Average distance and vertex-connectivity

Peter Dankelmann, Simon Mukwembi, Henda C. Swart

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


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., μ(G) = (n2)-1 σ{x,y}⊂V(G) d g(x,y), where V(G) denotes the vertex set of G and dG(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.

Original languageEnglish
Pages (from-to)157-177
Number of pages21
JournalJournal of Graph Theory
Issue number2
Publication statusPublished - Oct 2009
Externally publishedYes


  • Average distance
  • Connectivity
  • Distance
  • Radius

ASJC Scopus subject areas

  • Geometry and Topology


Dive into the research topics of 'Average distance and vertex-connectivity'. Together they form a unique fingerprint.

Cite this