Some New Sufficient Conditions for Graphs to be \((a, b, k)\)-Critical Graphs

Abstract

Let \(G\) be a graph, and let \(a\), \(b\) and \(k\) be nonnegative integers with \(1 \leq a \leq b\). 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 \(x \in V(G)\). Then a graph \(G\) is called an \((a, b, k)\)-critical graph if after any \(k\) vertices of \(G\) are deleted the remaining subgraph has an \([a, b]\)-factor. In this paper, three sufficient conditions for graphs to be \((a, b, k)\)-critical graphs are given. Furthermore, it is shown that the results in this paper are best possible in some sense.