2

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?

aellab
  • 429
  • 2
  • 9
  • 1
    This is relevant https://cstheory.stackexchange.com/q/16354/4896 – Sasho Nikolov May 27 '17 at 03:03
  • 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. – JimN May 30 '17 at 20:52
  • @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. – aellab May 31 '17 at 20:13

0 Answers0