## Abstract

Let G be a connected graph. The eccentricity, ECG(v), of a vertex v V(G) is the maximum distance between v and any other vertex in G, and the average eccentricity, avec(G), of G is the mean of the eccentricities of vertices in G. We prove that every 3-connected plane graph of order p and maximum face length I has a spanning tree T with average eccentricity at most p/4 +(25/48 l/p+ 5/6p+ 5/4) +1/3p+ 1. Furthermore, we extend this result to 4- and 5-connected plane graphs. We also construct graphs to show that the bounds are asymptotically sharp. In addition, we establish an asymptotically sharp upper bound on the average eccentricity of graphs in terms of order and size.

Original language | English |
---|---|

Pages (from-to) | 37-49 |

Number of pages | 13 |

Journal | Utilitas Mathematica |

Volume | 107 |

Publication status | Published - Jun 2018 |

## Keywords

- Average eccentricity
- Planar graph
- Spanning tree

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty
- Applied Mathematics