Average distance and vertex-connectivity

✍ Scribed by Peter Dankelmann; Simon Mukwembi; Henda C. Swart

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 202 KB
• Volume: 62
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20395

✦ Synopsis

Abstract

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