| Summary: | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mo>Γ</mo></semantics></math></inline-formula> be a connected graph of order at least 2, and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>S</mi><mo>\</mo><mi>V</mi><mo>(</mo><mo>Γ</mo><mo>)</mo></mrow></semantics></math></inline-formula>. Then, the minimum size among all the connected subgraphs whose vertex sets contain <i>S</i> is the <i>Steiner distance</i><inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>d</mi><mo>Γ</mo></msub><mrow><mo>(</mo><mi>S</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> among the vertices of <i>S</i>. The <i>Steiner k-eccentricity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>e</mi><mi>k</mi></msub><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula></i> of a vertex <i>v</i> of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mo>Γ</mo></semantics></math></inline-formula> is defined by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>e</mi><mi>k</mi></msub><mrow><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow><mo>=</mo><mo movablelimits="true" form="prefix">max</mo><mo>{</mo></mrow><msub><mi>d</mi><mo>Γ</mo></msub><mrow><mrow><mo>(</mo><mi>S</mi><mo>)</mo></mrow><mspace width="0.166667em"></mspace><mo>|</mo><mspace width="0.166667em"></mspace><mi>S</mi><mo>\</mo><mi>V</mi><mrow><mo>(</mo><mo>Γ</mo><mo>)</mo></mrow><mo>,</mo><mspace width="4pt"></mspace><mo>|</mo><mi>S</mi><mo>|</mo><mo>=</mo><mi>k</mi><mo>,</mo><mspace width="4pt"></mspace><mi>a</mi><mi>n</mi><mi>d</mi><mspace width="4pt"></mspace><mi>v</mi><mo>∈</mo><mi>S</mi><mo>}</mo></mrow></mrow></semantics></math></inline-formula>, where <i>n</i> and <i>k</i> are two integers, with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>2</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>n</mi></mrow></semantics></math></inline-formula>, and the <i>Steiner k-diameter</i> of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mo>Γ</mo></semantics></math></inline-formula> is defined by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo form="prefix">sdiam</mo><mi>k</mi></msub><mrow><mo>(</mo><mo>Γ</mo><mo>)</mo></mrow><mo>=</mo><mo movablelimits="true" form="prefix">max</mo><mrow><mo>{</mo><msub><mi>e</mi><mi>k</mi></msub><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow><mspace width="0.166667em"></mspace><mo>|</mo><mspace width="0.166667em"></mspace><mi>v</mi><mo>∈</mo><mi>V</mi><mrow><mo>(</mo><mo>Γ</mo><mo>)</mo></mrow><mo>}</mo></mrow></mrow></semantics></math></inline-formula>. In this paper, we present an algorithm to derive the Steiner distance of a graph; in addition, we obtain a relationship between the Steiner <i>k</i>-diameter of a graph and its line graph. We study various properties of the Steiner diameter through a combinatorial approach. Moreover, we characterize graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mo>Γ</mo></semantics></math></inline-formula> when <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo form="prefix">sdiam</mo><mi>k</mi></msub><mrow><mo>(</mo><mo>Γ</mo><mo>)</mo></mrow></mrow></semantics></math></inline-formula> is given, and we determine <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo form="prefix">sdiam</mo><mi>k</mi></msub><mrow><mo>(</mo><mo>Γ</mo><mo>)</mo></mrow></mrow></semantics></math></inline-formula> for some special graphs. We also discuss some of the applications of Steiner diameter, including one in education networks.
|
|---|