2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ This is relevant cstheory.stackexchange.com/q/16354/4896 $\endgroup$
    – Sasho Nikolov
    Commented May 27, 2017 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
    Commented May 30, 2017 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$
    – aellab
    Commented May 31, 2017 at 20:13

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.