The average eccentricity, spanning trees of plane graphs, size and order

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. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.