2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I guess that all edges have equal length? $\endgroup$ – Manfred Weis Jan 25 '18 at 5:01
  • 1
    $\begingroup$ What do you mean by random path? $\endgroup$ – Fedor Petrov Jan 25 '18 at 6:36
  • $\begingroup$ @FedorPetrov I have edited to make this more clear $\endgroup$ – Largest Prime Jan 25 '18 at 13:47
1
$\begingroup$

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$.

$\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.