Average distance and vertex‐connectivity

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 , i.e., $\mu(G)=\left(_{2}^{n}\right)^{-1}\sum_{\{x,y\}\subset V(G)}d_{G} (x,y)$ , where V ( G ) denotes the vertex set of G and d G ( x, y ) is the distance between x and y . We prove that if G is a κ ‐vertex‐connected graph, κ⩾3 an odd integer, of order n , then µ( G )⩽ n /2(κ + 1) + O (1). Our bound is shown to be best possible and our results, apart from answering a question of Plesník [J Graph Theory 8 (1984), 1–24], Favaron et al. [Networks 19 (1989), 493–504], can be used to deduce a theorem that is essentially equivalent to a theorem by Egawa and Inoue [Ars Combin 51 (1999), 89–95] on the radius of a κ ‐vertex‐connected graph of given order, where κ is odd. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 157–177, 2009