关于图是(g,f,n)-临界图的充分条件

设G是一个图. 设g和f是两个定义在V(G)上的整值函数使得对V(G)所有的顶点x有g(x)f(x). 图G被称为(g,f,n)-临界图,如果删去G的任意n个顶点后的子图都含有G的(g,f)-因子. 本文给出了图是(a,b,n)-临界图几个充分条件. 进一步指出这些条件是最佳的. 例如,如果对V(G)所有的顶点x和y都有g(x)＜f(x), n+g(x)dG(x)和g(x)/(dG(x)-n)f(y)/dG(y),则G是(g,f,n)-临界图.

Sufficient Conditions for Graphs to be (g,f,n)-critical Graphs

Let G be a graph, and let g and f be two integer-valued functions defined on V(G) such that g(x)f(x) for all x∈V(G). 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, sufficient conditions for graphs to be (g,f,n)-critical graphs are given. For example, we prove that a graph is a (g,f,n)-critical graph if g(x)＜f(x) and n+g(x)dG(x) for all x∈V(G) and g(x)/(dG(x)-n)f(y)/dG(y) for all adjacent vertices x and y of G.