Edge-grafting transformations on the average eccentricity of graphs and their applications

The average eccentricity of an n-vertex connected graph G=(VG,EG) is defined as ε̄(G)=1n∑x∈VGεG(x), where εG(x) is the eccentricity of the vertex x in G. Our main results in this paper are that some edge-grafting transformations are introduced and their effect on the average eccentricity are studied, respectively. This presents in a way a unified approach to the problem of finding trees with the maximum or minimum average eccentricity and given properties as follows: Sharp upper and lower bounds on the average eccentricity of n-vertex trees with k leaves are determined. The n-vertex tree with given domination number γ having the minimum average eccentricity is determined and n-vertex trees with domination number γ satisfying n=kγ having the maximum average eccentricity are identified, respectively, for k=2,3,n2,n3. The ordering of n-vertex trees with a given bipartition with respect to the average eccentricity is presented.