Average distance and edge-connectivity i

The average distance μ(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 if G is a λ-edge-connected graph of order n, then the bounds μ(G) ≤ 2n/15 + 9 if λ = 5, 6, μ(G) ≤ n/9 + 10 if λ = 7, and μ(G) ≤ n/(λ+1) + 5 if λ ≥ 8 hold. Our bounds are shown to be best possible, and our results solve a problem of Plesník [J. Graph Theory, 8 (1984), pp. 1-24].