A Result on $(a,b,k)$-Critical Graphs

Abstract

Let $G$ be a graph, and let $a$, $b$, $k$ be integers with $0\le a\le b$, $k\ge 0$. An $[a,b]$-factor of graph $G$ is defined as a spanning subgraph $F$ of $G$ such that $a\le d_F(v)\le b$ for each $v\in V(F)$. Then a graph $G$ is called an $(a,b,k)$-critical graph if after deleting any $k$ vertices of $G$ the remaining graph of $G$ has an $[a,b]$-factor. In this paper, it is proved that, if $a$, $b$, $k$ be integers with $1\le a<b$, $k\ge 0$ and $b\ge a(k+1)$ and $G$ is a graph with $\delta (G)\ge a+k$ and binding number $b(G)\ge a-1+\frac{a(k+1)}{b}$, then $G$ is an $(a,b,k)$-critical graph. Furthermore, it is shown that the result in this paper is best possible in some sense.