SOME TOUGHNESS RESULTS IN INDEPENDENT DOMINATION CRITICAL GRAPHS

作者：Ananchuen Nawarat; Ananchuen Watcharaphong^*

来源：Discussiones Mathematicae - Graph Theory, 2015, 35(4): 703-713.

DOI：10.7151/dmgt.1828

• domination critical
• toughness

A subset S of V(G) is an independent dominating set of G if S is independent and each vertex of G is either in S or adjacent to some vertex of S. Let i(G) denote the minimum cardinality of an independent dominating set of G. A graph G is k-i-critical if i(G) = k, but i (G + uv) < k for any pair of non-adjacent vertices a and a of G. In this paper, we establish that if G is a connected 3-i-critical graph and S is a vertex cutset of G with vertical bar S vertical bar >= 3, then omega(G - S) <= 1+root 8 vertical bar S vertical bar+1/2, improving a result proved by Ao [3], where omega(G - S) denotes the number of components of G - S. We also provide a characterization of the connected 3-i-critical graphs G attaining the maximum number of omega(G - S) when S is a minimum cutset of size 2 or 3.

• 出版日期2015