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?

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

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .