On a Combinatorial Approach to Studying the Steiner Diameter of a Graph and Its Line Graph - Hongfang Liu; Zhizhang Shen; Chenxu Yang; Kinkar Chandra Das (Mathematics, 2022)
In 1989, Chartrand, Oellermann, Tian and Zou introduced the Steiner distance for graphs. This is a natural generalization of the classical graph distance concept. Let <semantics>Γ</semantics> be a connected graph of order at least 2, and <semantics>S\V(Γ)</semantics>. Then, the minimum size among all the connected subgraphs whose vertex sets contain S is the Steiner distance<semantics>dΓ(S)</semantics> among the vertices of S. The Steiner k-eccentricity <semantics>ek(v)</semantics> of a vertex v of <semantics>Γ</semantics> is defined by <semantics>ek(v)=max{dΓ(S)<mspace width="0.166667em"></mspace>|<mspace width="0.166667em"></mspace>S\V(Γ),<mspace width="4pt"></mspace>|S|=k,<mspace width="4pt"></mspace>and<mspace width="4pt"></mspace>v∈S}</semantics>, where n and k are two integers, with <semantics>2≤k≤n</semantics>, and the Steiner k-diameter of <semantics>Γ</semantics> is defined by <semantics>sdiamk(Γ)=max{ek(v)<mspace width="0.166667em"></mspace>|<mspace width="0.166667em"></mspace>v∈V(Γ)}</semantics>. In this paper, we present an algorithm to derive the Steiner distance of a graph; in addition, we obtain a relationship between the Steiner k-diameter of a graph and its line graph. We study various properties of the Steiner diameter through a combinatorial approach. Moreover, we characterize graph <semantics>Γ</semantics> when <semantics>sdiamk(Γ)</semantics> is given, and we determine <semantics>sdiamk(Γ)</semantics> for some special graphs. We also discuss some of the applications of Steiner diameter, including one in education networks.