# Graphs for which the number of shortest paths between every pair of vertices is polynomially bounded

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?

• This is relevant cstheory.stackexchange.com/q/16354/4896 May 27 '17 at 3: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.
– mich
May 31 '17 at 20:13