Some Sufficient Conditions for Graphs to Be (g,f,n)-Critical Graphs
Sizhong Zhou, Hongxia Liu, Ziming Duan, Sio-Iong Ao, Alan H. S. Chan, Hideki Katagiri, Osca Castillo, Li Xu · AIP conference proceedings · 2009
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.