Mean distance in a graph

J. K. Doyle, Jack E Graver

Research output: Contribution to journalArticle

101 Scopus citations

Abstract

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
Volume17
Issue number2
DOIs
StatePublished - 1977

    Fingerprint

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

Cite this