A New Sufficient Condition for Graphs to be \((a, b, k)\)-Critical Graphs

Abstract

Let \(a, b\), and \(k\) be nonnegative integers with \(2 \leq a \leq 6\) and \(b \equiv 0 \pmod{a-1}\). Let \(G\) be a graph of order \(n\) with \(n \geq \frac{(a+b-1)(2a+b-4)-a+1}{b} + k\). A graph \(G\) is called an \((a, b, k)\)-critical graph if after deleting any \(k\) vertices of \(G\), the remaining graph has an \([a, b]\)-factor. In this paper, it is proved that \(G\) is an \((a, b, k)\)-critical graph if and only if \[|N_G(X)| >\frac{(a-1)n + |X| + bk-1}{a+b-1} \] for every non-empty independent subset \(X\) of \(V(G)\), and \[\delta(G) > \frac{(a-1)n + b + bk}{a+b-1}.\] Furthermore, it is shown that the result in this paper is best possible in some sense.