1
$\begingroup$

If $G$ is a finite, connected simple graph then is there an expression for the average geodesic length?

That is suppose I know two nodes $n_1$ and $n_2$, the number of edges in my graph and at those points and the number of vertices then is there a formula giving reasonable bounds on the geodesic connecting $n_1$ to $n_2's$ length?

$\endgroup$
2
  • $\begingroup$ What do you mean by a complete graph? Isn't length always $1$ there? $\endgroup$ May 26, 2016 at 14:57
  • $\begingroup$ I meant connected $\endgroup$
    – ABIM
    May 26, 2016 at 15:01

1 Answer 1

2
$\begingroup$

There is no formula depending just on the number of vertices (or even the number of vertices plus number of edges), and for a $d$-regular graph, for example, the average could range anywhere from linear in the number of vertices to logarithmic - this has to do with the expansion properties of the graph.

$\endgroup$
3
  • $\begingroup$ Interesting... could you elaborate or provide a reference? Thanks $\endgroup$
    – ABIM
    May 26, 2016 at 16:43
  • 1
    $\begingroup$ @CSA Well, for example, in a cycle graph, the average path length is linear (you can increase the degree by growing "hair" out of the graph.) In a $d$-regular tree, the average distance is logarithmic. An expander graph (look at the wikipedia article, e.g.) looks a lot like a tree... $\endgroup$
    – Igor Rivin
    May 26, 2016 at 17:40
  • $\begingroup$ Perfect, thanks Igor (I was hoping there would be some deep explanatory result but i guess there does not seem to be one). Thanks again Igor. $\endgroup$
    – ABIM
    May 26, 2016 at 18:50

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.