Average Distance and Edge-Connectivity II
Peter Dankelmann, Simon Mukwembi, Henda C. Swart · SIAM Journal on Discrete Mathematics · 2008
The average distance $\mu(G)$ of a connected graph G of order n is the average of the distances between all pairs of vertices of G. We prove that for a 3-edge-connected graph G of order n the inequality $\mu(G)\le{n}/{6}+24$ on the average distance holds. Our bound is shown to be best possible even if G is 4-edge-connected, and our results answer, in part, a question of Plesník [J. Graph Theory, 8 (1984), pp. 1–24].