Steiner distance stable graphs

✍ Scribed by Wayne Goddard; Ortrud R. Oellermann; Henda C. Swart

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 673 KB
• Volume: 132
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)90232-1

✦ Synopsis

Let G be a connected graph and S a nonempty set of vertices of G. Then the Steiner distance d,(S) of S is the smallest number of edges in a connected subgraph of G that contains S. Let k, I, s and m be nonnegative integers with m > s > 2 and k and I not both 0. Then a connected graph G is said to be k-vertex I-edge (s,m)-Steiner distance stable, if for every set S of s vertices of G with d,(S) = m, and every set A consisting of at most k vertices of G-S and at most I edges of G, dG_A(S) =d,(S). It is shown that if G is k-vertex I-edges (s, m)-Steiner distance stable, then G is k-vertex I-edge (s, m + 1)-Steiner distance stable. Further, a k-vertex I-edge (s, m)-Steiner distance stable graph is shown to be a k-vertex I-edge (s -1, m)-Steiner distance stable graph for s > 3. It is then shown that the converse of neither of these two results holds. If G is a connected graph and S an independent set of s vertices of G such that d,(S) = m, then S is called an I(s, m)-set. A connected graph is k-vertex I-edge I(s, m)-Steiner distance stable if for every I(s, m)-set S and every set A of at most k vertices of G-S and I-edges of G, dc_A(S) = m. It is shown that a k-vertex I-edge 1(3, m)-Steiner distance stable graph, m>4, is k-vertex I-edge 1(3, m + 1)-Steiner distance stable.