The Steiner k-eccentricity on trees

• DOI: 10.1016/j.tcs.2021.08.010
• Publication Date: 2021-08-12T14:54:47Z
• Authors: Xingfu Li; Guihai Yu; Sandi Klavžar; Jie Hu; Bo Li
• Keywords: Steiner tree problem; Eccentricity (behavior); Tree (set theory)

We study the Steiner $k$-eccentricity on trees, which generalizes the previous one in the paper [X.~Li, G.~Yu, S.~Klav��ar, On the average Steiner 3-eccentricity of trees, arXiv:2005.10319, 2020]. To support the algorithm, we achieve much stronger properties for the Steiner $k$-ecc tree than that in the previous paper. Based on this, a linear time algorithm is devised to calculate the Steiner $k$-eccentricity of a vertex in a tree. On the other hand, the lower and upper bounds of the average Steiner $k$-eccentricity index of a tree on order $n$ are established based on a novel technique which is quite different from that in the previous paper but much easier to follow.