Mean distance in a graph

J. K. Doyle; J. E. Graver

doi:10.1016/0012-365X(77)90144-3

Mean distance in a graph

J. K. Doyle, J. E. Graver

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

138 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 language	English (US)
Pages (from-to)	147-154
Number of pages	8
Journal	Discrete Mathematics
Volume	17
Issue number	2
DOIs	https://doi.org/10.1016/0012-365X(77)90144-3
State	Published - 1977

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

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

Cite this

@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, {J. 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, J. 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

AN - SCOPUS:49449129161

SN - 0012-365X

VL - 17

SP - 147

EP - 154

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

Mean distance in a graph

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this