# Asymptotic formula for average geodesic length on graph?

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?

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

## 1 Answer

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.

• Interesting... could you elaborate or provide a reference? Thanks May 26 '16 at 16:43
• @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... May 26 '16 at 17:40
• 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. May 26 '16 at 18:50