Mean distance in a graph

J. K. Doyle, J. E. Graver

Research output: Contribution to journalArticlepeer-review

136 Scopus citations


The average or mean of the distances between vertices in a connected graph Γ, μ(Γ), is a natural measure of the compactness of the graph. In this paper we compute bounds for μ(Γ) in terms of the number of vertices in Γ and the diameter of Γ. We prove a formula for computing μ(Γ) when Γ is a tree which is particularly useful when Γ has a high degree of symmetry. Finally, we present algorithms for μ(Γ) which are amenable to computer implementation.

Original languageEnglish (US)
Pages (from-to)147-154
Number of pages8
JournalDiscrete Mathematics
Issue number2
StatePublished - 1977

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Mean distance in a graph'. Together they form a unique fingerprint.

Cite this