Average distance and edge-connectivity i

Peter Dankelmann, Simon Mukwembi, Henda C. Swart

Research output: Contribution to journalArticlepeer-review

16 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. 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].

Original languageEnglish
Pages (from-to)92-101
Number of pages10
JournalSIAM Journal on Discrete Mathematics
Issue number1
Publication statusPublished - 2008
Externally publishedYes


  • Average distance
  • Distance
  • Edge-connectivity

ASJC Scopus subject areas

  • General Mathematics


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

Cite this