The Steiner k-eccentricity on trees

DOI10.1016/J.TCS.2021.08.010zbMATH Open1487.68182arXiv2008.07763OpenAlexW3190354932MaRDI QIDQ2232615FDOQ2232615

Xingfu Li, Jie Hu, Guihai Yu, Bo Li, Sandi Klavžar

Publication date: 6 October 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We study the Steiner $k$-eccentricity on trees, which generalizes the previous one in the paper [X.~Li, G.~Yu, S.~Klavv{z}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.

Full work available at URL: https://arxiv.org/abs/2008.07763

Recommendations

• On the average Steiner 3-eccentricity of trees
• Bounding the \(k\)-Steiner Wiener and Wiener-type indices of trees in terms of eccentric sequence
• Extremal trees of a given degree sequence or segment sequence with respect to average Steiner 3-eccentricity
• scientific article; zbMATH DE number 1394667
• scientific article; zbMATH DE number 687700

zbMATH Keywords

graph algorithmsSteiner distanceSteiner treeSteiner eccentricity

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Distance in graphs (05C12) Paths and cycles (05C38)

Cites Work

• Introduction to algorithms
• Title not available (Why is that?)
• The Steiner tree problem
• On the average Steiner distance of graphs with presribed properties
• The Steiner Wiener index of a graph
• Steiner distance in graphs
• The average Steiner distance of a graph
• Upper bounds on the average eccentricity
• Title not available (Why is that?)
• On the extremal properties of the average eccentricity
• Convex sets in lexicographic products of graphs
• Inverse problem on the Steiner Wiener index
• On the Steiner median of a tree
• Title not available (Why is that?)
• On Steiner degree distance of trees
• A sharp lower bound on Steiner Wiener index for trees with given diameter
• Steiner Distance in Product Networks
• Steiner convex sets and Cartesian product
• On the average Steiner 3-eccentricity of trees
• On the Steiner hyper-Wiener index of a graph
• Title not available (Why is that?)
• Steiner (revised) Szeged index of graphs
• Isometric subgraphs for Steiner distance

Cited In (5)

• The average Steiner \(( 3 , 2 )\)-eccentricity of trees
• A note on the Steiner \(k\)-radius and Steiner \(k\)-diameter
• k-Eccentricity and absolute k-centrum of a probabilistic tree
• Title not available (Why is that?)
• Extremal trees of a given degree sequence or segment sequence with respect to average Steiner 3-eccentricity

This page was built for publication: The Steiner \(k\)-eccentricity on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2232615)