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 | |
| State | Published - 1977 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
Fingerprint Dive into the research topics of 'Mean distance in a graph'. Together they form a unique fingerprint.
Cite this
Doyle, J. K., & Graver, J. E. (1977). Mean distance in a graph. Discrete Mathematics, 17(2), 147-154. https://doi.org/10.1016/0012-365X(77)90144-3