Mean distance in a graph

J. K. Doyle, Jack E Graver

Research output: Contribution to journalArticle

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 language English (US) 147-154 8 Discrete Mathematics 17 2 https://doi.org/10.1016/0012-365X(77)90144-3 Published - 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 journalArticle

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 -