2025/11/27 by Q. H. Zhang, Zhang, Qingnan, Yingzhi Tian +1
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2511.22492
openalex publication_date 2025/11/27 · openalex created_date 2025/12/03 · openalex updated_date 2026/07/28
Given a connected graph G=(V,E) and a k-set S⊆ V(G), the Steiner distance dG(S) of S is defined as the size of a minimum tree including S in G. The Steiner k-eccentricity of a vertex v in G is the maximum value of dG(S) over all S⊆ V(G) with |S|=k and v∈ S. The minimum Steiner k-eccentricity over all vertices, denoted by Srk(G), is called the Steiner k-radius of G and the maximum Steiner k-eccentricity over all vertices, denoted by Sdk(G), is its Steiner k-diameter. The Steiner (k,k′)-eccentricity of a k′-subset S′ of V(G), which is an extension of the Steiner k-eccentricity of a vertex v, is defined as the maximum Steiner distance over all k-subsets of V(G) containing S′. The minimum Steiner (k,k′)-eccentricity among all k′-subsets of V(G), denoted by Srk,k′(G), is called the Steiner (k,k′)-radius of G. In 1989, Chartrand, Oellermann, Tian and Zou showed that for any k≥3, Sdk(T)≤ (k)/(k-1)Srk(T) for any tree T. In this paper, we generalize this result and show that Sdk(T)≤ \frackk-k′Srk,k′(T) for any k≥3, k>k′≥1. Furthermore, for k′=2 and k′=3, we obtain a tight upper bound of the Steiner k-diameter by the Steiner (k,k′)-radius for all trees.