A characterization of maximal non-\(k\)-factor-critical graphs (Q861799)

A graph \(G\) of order \(p\) is \(k\)-factor critical, where \(p\) and \(k\) are integers with similar parity, if deleting any \(k\) vertices yields a graph with a perfect matching. \(G\) is maximal non-\(k\)-factor critical if \(G\) is not \(k\)-factor critical but \(G+e\) is \(k\)-factor critical for every edge \(e\) not in the edge set of \(G\). Closely related concepts are those of a \(k\)-extendable graph and a maximal non-\(k\) extendable graph. This paper gives complete characterizations of maximal non-\(k\)-factor critical graphs and maximal non-\(k\)-extendable graphs.