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?

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

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.

  • $\begingroup$ Interesting... could you elaborate or provide a reference? Thanks $\endgroup$ – AIM_BLB May 26 '16 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 '16 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$ – AIM_BLB May 26 '16 at 18:50

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.