×

Degree conditions of ID-factor-critical graphs. (English) Zbl 1052.05060

Summary: We say that a simple graph \(G\) is independent-set-deletable factor-critical, shortly, ID-factor-critical, if \(G-I\) has a perfect matching for every independent set \(I\) of \(G\) which has the same parity with \(| V(G)|\). Degree conditions of ID-factor-critical graphs are researched in this paper. The main results are as follows: (1) \(\lceil\frac{2n-1}{3}\rceil\) is the minimum integer \(\delta\) such that every graph with minimum degree at least \(\delta\) and \(n\) vertices is ID-factor-critical. (2) If \(n\equiv 1\pmod 3\) and \(\frac{n-1} {2}\) is odd, then \(\lceil\frac{2n+1} {3}\rceil\) is the minimum integer \(k\) such that, for \(k'\geq k\), every \(k'\)-regular graph with \(n\) vertices is ID-factor-critical, otherwise, \(\lceil\frac{2n-3} {2}\rceil\) is the minimum integer \(k\) such that, for \(k'\geq k\), every \(k'\)-regular graph with \(n\) vertices is ID-factor-critical, where \(n\geq 7\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite