Back to Search
Start Over
Extremal trees of a given degree sequence or segment sequence with respect to average Steiner 3-eccentricity.
- Source :
-
Applied Mathematics & Computation . Feb2023, Vol. 438, pN.PAG-N.PAG. 1p. - Publication Year :
- 2023
-
Abstract
- • Show that an interesting transformation on trees is monotone with respect to the average Steiner 3-eccentricity. • Establish some sharp bounds on the average Steiner 3-eccentricity among trees with a given degree sequence (resp. segment sequence, number of segments). • Using the majorization theory and our obtained results to characterize extremal graphs among the trees with some given classical parameters. 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 , Δ be the set of n -vertex trees with maximum degree Δ , T n , Δ k be the set of n -vertex trees with exactly k vertices of a given maximum degree Δ , and let MT n k 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 , Δ k (resp. T n , Δ , MT n k , 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *STEINER systems
*TREES
*TREE graphs
Subjects
Details
- Language :
- English
- ISSN :
- 00963003
- Volume :
- 438
- Database :
- Academic Search Index
- Journal :
- Applied Mathematics & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 159822270
- Full Text :
- https://doi.org/10.1016/j.amc.2022.127556