<p>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 (<a href="https://en.wikipedia.org/wiki/Block_graph" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Block_graph</a>), for example.</p>

<p>Is there a name for this class of graphs? Is anything known about it?</p>

CC BY-SA 3.0
2017-05-27T03:03:12.070Z
This is relevant https://cstheory.stackexchange.com/q/16354/4896
Sasho Nikolov
CC BY-SA 3.0
2017-05-30T20:52:40.973Z
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
CC BY-SA 3.0
2017-05-31T20:13:02.433Z
@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
<reference-request><graph-theory>
Graphs for which the number of shortest paths between every pair of vertices is polynomially bounded
aellab
# Graphs for which the number of shortest paths between every pair of vertices is polynomially bounded

(Asked by: username_0 on 2017-05-26)

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?

**Tags:** reference-request, graph-theory

> **Comments:**
> **username_1**: This is relevant https://cstheory.stackexchange.com/q/16354/4896  
> **username_2**: 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.  
> **username_0**: @username_2astos 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.  

---

## 0 answers

