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

Abstract

Let \(G\) be a graph, and let \(a\), \(b\), \(k\) be integers with \(0 \leq a \leq b\), \(k \geq 0\). An \([a, b]\)-factor of graph \(G\) is defined as a spanning subgraph \(F\) of \(G\) such that \(a \leq d_F(v) \leq 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 \leq a < b\), \(k \geq 0\) and \(b \geq a(k+1)\) and \(G\) is a graph with \(\delta(G) \geq a+k\) and binding number \(b(G) \geq 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.