The minimum Steiner k-eccentricity

By Josiah Reiswig

29 March 2019

Given a connected graph G=(V,E) and a vertex set S⊂ V, the Steiner distance d(S) of S is the size of a minumum spanning tree of S in G. For a connected graph G of order n and an integer k with 2≤ k ≤ n, the Steiner k-eccentricity of v of a vertex v in G is the maximum value of d(S) over all S⊂ V with |S|=k and v∈ S. The minimum Steiner k-eccentricity, sradk(G), is called the Steiner k-radius of G and the maximum Steriner k-eccentricity, sdiamk(G), is called the Steiner k-diameter of G. In 1990, Henning, Oellermann, and Swart showed that for any integer k≤ 2, there exists a graph G_k such that sdiam_k(G_k)=(2(k+1))/(2k-1)sradk(Gk) and proved that sdiam3(G)≤ 8/5srad3(G), and sdiam4(G)≤ 10/7srad3(G) for all connected graphs G. In this talk, we will show that for each k≤ 5, sdiamk(G)≤ (k+3)/(k+1)sradk(G) and show that this bound is tight via a construction.