×

Maximal non-ID-factor-critical graphs. (English) Zbl 1045.05072

Summary: We say that a simple graph \(G\) is independent-set-deletable factor-critical, shortly ID-factor-critical, if for every independent set \(I\) of \(G\) whose size has the same parity with \(| V(G)|\), \(G-I\) has a perfect matching. A simple graph \(G\) is maximal non-ID-factor-critical if \(G\) is not ID-factor-critical and \(G+xu\) is ID-factor-critical for every two nonadjacent vertices \(x\) and \(y\). In this paper, we characterize the maximal non-ID-factor-critical graphs.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

independent set
PDFBibTeX XMLCite