3
$\begingroup$

Let $G$ be a simple undirected graph, and let $s$ and $t$ be two arbitrary vertices of $G$. Even for some rather restricted graph classes, the number of shortest paths between $s$ and $t$ can be exponential in the size of $G$. However, for some graph classes like block graphs, the number of shortest paths between $s$ and $t$ is 1 (such graphs are known as geodetic graphs).

For what graph classes $G$ is it true that between any pair of vertices $s$ and $t$ of $G$, the number of shortest paths between $s$ and $t$ is bounded from above by $\text{poly}(n,m)$? Here, $n$ is the number of vertices, and $m$ the number of edges.

For example, are there graphs (other than block graphs) that would have a constant number of shortest paths between any pair of vertices?

$\endgroup$
1
$\begingroup$

For your first question, you might be interested in the class of strongly regular graphs.

For your second question, cycles of odd length work since any two vertices have a unique shortest path between them. Actually any such (simple) graph would have to be either edgeless or geodetic since adjacent vertices have a unique shortest path between them.

$\endgroup$
0
$\begingroup$

The class of geodetic graphs includes trees, and indeed block graphs, that generalize trees.

A graph is bigeodetic if there are at most 2 shortest paths between any pair of vertices. The class of bigeodetic graphs contain geodetic graphs and interval-regular graphs of diameter two in which every pair of non-adjacent vertices has exactly two paths of length two between them. The cycle graph is another example.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.