Let $G$ be a graph with $n$ vertices and $m$ edges, such that for every two vertices $u$ and $v$, the number of shortest paths from $u$ to $v$ is bounded by some polynomial $poly(n,m)$ in $n$ and $m$. A class of graphs which have this property are block graphs (https://en.wikipedia.org/wiki/Block_graph), for example.

Is there a name for this class of graphs? Is anything known about it?

  • 1
    $\begingroup$ This is relevant cstheory.stackexchange.com/q/16354/4896 $\endgroup$ – Sasho Nikolov May 27 '17 at 3:03
  • $\begingroup$ This definition, as given, can't be applied to a single graph - it needs to be modified to apply to a class/family of graphs. Or you could say: Let G be a graph with #v=n_G,#e=m_G , and let numpath(G) be the largest number of paths between any two vertices in G. Then you are asking for classes of graphs for which numpath(G) is bounded by a single polynomial in n_G and m_G for every G in the class. $\endgroup$ – JimN May 30 '17 at 20:52
  • $\begingroup$ @JimNastos For sure, it is not a precise definition; I am thinking of it as applied to a family of graphs, but the question itself is meant in an open-ended sense. $\endgroup$ – mich May 31 '17 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.