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 -