A New Sufficient Condition for a Graph To Be (g, f, n)-Critical

作者：Zhou, Sizhong^*

来源：Canadian Mathematical Bulletin, 2010, 53(2): 378-384.

DOI：10.4153/CMB-2010-034-8

• graph
• (g, f)-factor
• (g, f, n)-critical graph
• binding number

Let G be a graph of order p, let a, b, and n be nonnegative integers with 1 <= a < b, and let g and f be two integer-valued functions defined on V(G) such that a <= g(x) < f(x) <= b for all x is an element of V(G). A (g, f)-factor of graph G is a spanning subgraph F of G such that g(x) <= d(F)(x) <= f(x) for each x is an element of V (F). Then a graph G is called (g, f, n)-critical if after deleting any n vertices of G the remaining graph of G has a (g, f)-factor. The binding number bind(G) of G is the minimum value of |N(G)(X)|/|X| taken over all non-empty subsets X of V(G) such that N(G)(X) not equal V(G). In this paper, it is proved that G is a (g, f, n)-critical graph if
bind(G) > (a + b - 1)(p - 1)/(a + 1)p - (a + b) - bn + 2 and p >= (a + b - 1)(a + b - 2)/(a + 1) + bn/a
Furthermore, it is shown that this result is best possible in some sense.

• 出版日期2010-6
• 单位江苏科技大学