Let $G$ be a directed graph that has $n$ nodes and is strongly connected. Define a random path as the following: Pick two vertices uniformly at random and find the shortest path going from one vertex to another (either way is fine). Can we bound the length of a random path of $G$ if we know the size of $|E|$?

For example, if $E = O(n)$, then it seems easy to construct a graph with only large paths. However, if $E = \Theta(n^2)$, then it is likely that the graph has short expected path size. What if $|E| = o(n^2)$ or $O(n \log n)$ ? Can we derive any bounds for the expected length of a random path in these cases? What if our graph is undirected?

  • $\begingroup$ I guess that all edges have equal length? $\endgroup$ Commented Jan 25, 2018 at 5:01
  • 1
    $\begingroup$ What do you mean by random path? $\endgroup$ Commented Jan 25, 2018 at 6:36
  • $\begingroup$ @FedorPetrov I have edited to make this more clear $\endgroup$ Commented Jan 25, 2018 at 13:47

1 Answer 1


Even if $E$ grows as $cn^2$, the random path may have length about $n$. Consider a complete graph on $n/2$ vertices joined with a path of length $n/2$.


Your Answer

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

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