Binding Numbers and $(a,b,k)$-Critical Graphs

Abstract

Let $G$ be a graph of order $n$, and let $a,b,k$ be nonnegative integers with $1\le a\le b$. A spanning subgraph $F$ of $G$ is called an $[a,b]$-factor if $a\le d_F(x)\le b$ for each $x\in V(G)$. Then a graph $G$ is called an $(a,b,k)$-critical graph if $G–N$ has an $[a,b]$-factor for each $N\subseteq V(G)$ with $|N|=k$. In this paper, it is proved that $G$ is an $(a,b,k)$-critical graph if $n\ge \frac{(a+b-1)(a+b-2)}{b}+\frac{bk}{b-1}$, $bind(G)\ge \frac{(a+b-1)(n-1)}{b(n-1-k)}$, and $\delta (G)\ne \lfloor \frac{(a-1)n+a+b+bk-2}{a+b-1}\rfloor$.