The average eccentricity of a graph and its subgraphs

Abstract

The eccentricity of a vertex is the maximum distance from it to another vertex and the average eccentricity of a graph is the mean eccentricity of a vertex. In this paper we establish bounds on the mean eccentricity of a graph. We then examine the change in the average eccentricity when a graph is replaced by a spanning subgraph, in particular the two extreme cases: taking a spanning tree and removing one edge.