TY - JOUR

T1 - Mean distance in a graph

AU - Doyle, J. K.

AU - Graver, J. E.

N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

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

AN - SCOPUS:49449129161

VL - 17

SP - 147

EP - 154

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 2

ER -