Closure and factor-critical graphs (Q1974532)

A graph \(G\) is said to be \(n\)-factor-critical if \(G\setminus T\) has a perfect matching for each \(T\subset V(G)\) with \(|T|= n\). There is a close relationship between \(n\)-factor-criticality and matching extension. For every integer \(n\), \(0\leq n<|V(G)|/2\), a graph \(G\) is said to be \(n\)-extendable if \(G\) has a matching of size \(n\) and every matching of size \(n\) extends to a perfect matching of \(G\). \textit{O. Favaron} [Discuss. Math., Graph Theory 16, No. 1, 41-51 (1996; Zbl 0865.05061)] remarked that a \(2n\)-factor-critical graph is \(n\)-extendable. Here the authors study the relationship between \(n\)-factor-criticality and various closure operations which are usually considered in the theory of Hamiltonian graphs. For example, they show the following Bondy-Chvátal-type closure result. Theorem. Let \(G\) be a graph of order \(p\) and let \(x\) and \(y\) be a pair of distinct nonadjacent vertices of \(G\) with \(\deg_G x+\deg_G y\geq p+ n-1\). Then \(G\) is \(n\)-factor-critical if and only if \(G+ xy\) is \(n\)-factor-critical. The authors also investigate relationships between the various closures and matching extension.