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?

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

1 Answer 1

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Interesting... could you elaborate or provide a reference? Thanks $\endgroup$
    – ABIM
    Commented 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
    Commented 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
    Commented May 26, 2016 at 18:50

You must log in to answer this question.

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