Some results related to the toughness of 3-domination critical graphs. II
Abstract
A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k - 1 vertices. The structure of k-γ-critical graphs remains far from completely understood when γ ≥ 3. In a 1983 paper, Sumner and Blitch [SB] proved a theorem which may be regarded as a result related to the toughness of a 3-γ-critical graph and which says that if S is any vertex cutset of such a graph, then G - S has at most |S| + 1 components. In two previous papers, one by Chen, Tian and Wei [CTW] and the other by the present two authors [AP1], the Sumner-Blitch result was considerably extended. Let G be a graph of order n and let k be a non-negative integer. Then graph G is k-factor-critical if G - S has a perfect matching for every subset S ⊆ V(G) with |S| = k. In another previous paper [AP2], the present authors used the results of [CTW] and [AP1] to show that under certain assumptions regarding connectivity and minimum degree, a 3-γ-critical graph will be either 1-factor-critical or 2-factor-critical, according to the parity of n. In a parallel manner, in a forthcoming paper [AP3] the results of the present work are used to extend the results of [AP2] to the collection of 3-factor-critical graphs.
