Extremal trees of a given degree sequence or segment sequence with respect to average Steiner 3-eccentricity

摘要

The Steiner k-eccentricity of a vertex in a graph G is the maximum Steiner distance over all k-subsets containing the vertex. The average Steiner k-eccentricity of G is the mean value of all vertices' Steiner k-eccentricities in G. Let T-n be the set of all n-vertex trees, T-n,T-Delta be the set of n-vertex trees with maximum degree Delta, T-n,Delta(k) be the set of n-vertex trees with exactly k vertices of a given maximum degree Delta, and let MTnk be the set of n-vertex trees with exactly k vertices of maximum degree. In this paper, we first determine the sharp upper bound on the average Steiner 3-eccentricity of n-vertex trees with a given degree sequence. The corresponding extremal graphs are characterized. Consequently, together with majorization theory, all graphs among T-n,Delta(k) (resp. T-n,T-Delta, MTnk, T-n) having the maximum average Steiner 3-eccentricity are identified. Then we characterize the unique n-vertex tree with a given segment sequence having the minimum average Steiner 3-eccentricity. Finally, we determine all n-vertex trees with a given number of segments having the minimum average Steiner 3-eccentricity.

关键词