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