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