Minimum Degree Conditions for Graphs to be (g, f, n)-Critical Graphs
Sizhong Zhou · 2008
Abstract—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 ∈ V (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. Index Term−graph, minimum degree, (g,f)-factor, (g,f, n)-critical graph 1