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

Abstract

Let $a,b$, and $k$ be nonnegative integers with $2\le a\le 6$ and $b\equiv 0(\mathrm{mod}a-1)$. Let $G$ be a graph of order $n$ with $n\ge \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.