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

The average eccentricity of an n-vertex connected graph G = (V-G, E-G) is defined as (epsilon) over bar (G) = 1/n Sigma(x is an element of VG)epsilon(G)(x), where epsilon(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 gamma having the minimum average eccentricity is determined and n-vertex trees with domination number gamma satisfying n = k gamma having the maximum average eccentricity are identified, respectively, for k = 2, 3, n/2, n/3. The ordering of n-vertex trees with a given bipartition with respect to the average eccentricity is presented. (C) 2017 Elsevier B.V. All rights reserved.