Neighborhood unions and factor critical graphs Original Research Article

A graph G is said to be n-factor-critical if G−T has a perfect matching for each T⊂V(G) with |T|=n. In this note we give a sufficient condition for a graph to be n-factor-critical. Let G be a k-connected graph of order p, and let n be an integer with 0⩽n⩽k and p≡n (mod 2) and α be a real number with 12⩽α⩽1. We prove that if |NG(A)|>α(p−2k+n−2)+k for every independent set A of G with |A|=⌊α(k−n+2)⌋, then G is n-factor-critical. We also discuss the sharpness of the result and the relation with matching extension.