Notes on the binding numbers for (a,b,k)-critical graphs

作者：Zhou Sizhong^*; Jiang Jiashang

来源：Bulletin of the Australian Mathematical Society, 2007, 76(2): 307-314.

Let G be a graph of order n, and let a, b, k be nonnegative integers with 1 <= a < b. An [a, b]-factor of graph G is defined as a spanning subgraph F of G such that a <= d(F)(X) <= b for each x is an element of 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 G is an (a, b, k)-critical graph if the binding number
bind(G) > (a + b - 1)(n - 1)/bn - (a + b) - bk + 2
and
n >= (a + b - 1)(a + b - 2)/b + bk/b-1.
Furthermore, it is showed that the result in this paper is best possible in some sense.

• 出版日期2007-10
• 单位江苏科技大学