Mean distance in a graph

J. K. Doyle, Jack E Graver

Research output: Contribution to journal › Article

101 Citations (Scopus)

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

Compactness
Connected graph
Symmetry
Computing
Graph in graph theory

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

Cite this

Mean distance in a graph. / Doyle, J. K.; Graver, Jack E.

In: Discrete Mathematics, Vol. 17, No. 2, 1977, p. 147-154.

Research output: Contribution to journal › Article

Doyle, JK & Graver, JE 1977, 'Mean distance in a graph', Discrete Mathematics, vol. 17, no. 2, pp. 147-154. https://doi.org/10.1016/0012-365X(77)90144-3
Doyle JK, Graver JE. Mean distance in a graph. Discrete Mathematics. 1977;17(2):147-154. https://doi.org/10.1016/0012-365X(77)90144-3
Doyle, J. K. ; Graver, Jack E. / Mean distance in a graph. In: Discrete Mathematics. 1977 ; Vol. 17, No. 2. pp. 147-154.
@article{00ff4d2a2e2e477da3457d19451ff3be,
title = "Mean distance in a graph",
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.",
author = "Doyle, {J. K.} and Graver, {Jack E}",
year = "1977",
doi = "10.1016/0012-365X(77)90144-3",
language = "English (US)",
volume = "17",
pages = "147--154",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "2",

}

TY - JOUR

T1 - Mean distance in a graph

AU - Doyle, J. K.

AU - Graver, Jack E

PY - 1977

Y1 - 1977

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=49449129161&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=49449129161&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(77)90144-3

DO - 10.1016/0012-365X(77)90144-3

M3 - Article

VL - 17

SP - 147

EP - 154

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 2

ER -

Access to Document