Search

Let G be a graph of order p, and let a and 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 &sin; (G). A (g, f)-factor of graph G is defined as a spanning subgraph F of G such that g(x) ≤ dF (x) ≤ f(x) for each x . V (G). Then a graph G is called a (g, f, n)-critical graph if after deleting any n vertices of G the remaining graph of G has a (g, f)-factor. In this paper, we prove that every graph G is a (g, f, n)- critical graph if its minimum degree is greater than p+a+b-2√(a +1)p - bn + 1. Furthermore, it is showed that the result in this paper is best possible in some sense. [ABSTRACT FROM AUTHOR]