### 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 |

### Fingerprint

### ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Theoretical Computer Science

### Cite this

*Discrete Mathematics*,

*17*(2), 147-154. https://doi.org/10.1016/0012-365X(77)90144-3

**Mean distance in a graph.** / Doyle, J. K.; Graver, Jack E.

Research output: Contribution to journal › Article

*Discrete Mathematics*, vol. 17, no. 2, pp. 147-154. https://doi.org/10.1016/0012-365X(77)90144-3

}

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

AN - SCOPUS:49449129161

VL - 17

SP - 147

EP - 154

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 2

ER -