A new sufficient condition for graphs to be (a, b, k)-critical graphs

作者：Zhou, Sizhong^*

来源：Ars Combinatoria, 2015, 118: 191-199.

• graph
• neighborhood
• minimum degree
• [a, b]-factor
• (a, b, k)-critical graph

Let a, b and k be nonnegative integers with 2 <= a < b and b equivalent to 0 (mod a 1), and let G be a graph of order n with n >= (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 of G has an [a, b]-factor. In this paper, it is proved that G is an (a, b, k)-critical graph if
vertical bar NG(X)vertical bar > (a - 1)n + vertical bar X vertical bar + bk - 1/a + b - 1
for every non-empty independent subset X of V(G), and
delta(G) > (a - 1)n + b + bk/a + b - 1
Furthermore, it is shown that the result in this paper is best possible in some sense.

• 出版日期2015-1
• 单位江苏科技大学