On a Combinatorial Approach to Studying the Steiner Diameter of a Graph and Its Line Graph

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 Γ be a connected graph of order at least 2, and S \ V ( Γ ) . Then, the minimum size among all the connected subgraphs whose vertex sets contain S is the Steiner distance d Γ ( S ) among the vertices of S . The Steiner k-eccentricity e k ( v ) of a vertex v of Γ is defined by e k ( v ) = max { d Γ ( S ) | S \ V ( Γ ) , | S | = k , a n d v ∈ S } , where n and k are two integers, with 2 ≤ k ≤ n , and the Steiner k-diameter of Γ is defined by sdiam k ( Γ ) = max { e k ( v ) | v ∈ V ( Γ ) } . 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 Γ when sdiam k ( Γ ) is given, and we determine sdiam k ( Γ ) for some special graphs. We also discuss some of the applications of Steiner diameter, including one in education networks.