有1-因子的图和(g,f)-对等图

Graphs with 1-Factors and (g,f)-Uniform Graphs

既是(g,f)-覆盖又是(g,f)-消去的图称为(g,f)-对等图.给出了有1-因子F的图是(g,f)-对等图、f-对等图的关于F的分支的若干充分条件,证明了如下定理:设G是一个图,F为G的1-因子,w(F)≥2且w(F)≡0(mod 2);g和f是定义在V(G)上的整数值函数并且对每个x∈V(G)都有g(x)≤f(x).若对F的每个分支C=xy,G-{x,y}是(g,f)-对等图,则G也是(g,f)-对等图.并指出定理中的条件在一定意义上是最好可能的.

If a graph is （g,f）-covered and （g,f）-deleted, then it is called a （g,f）-uniform graph. Several sufficient conditions about components of factor F for graphs with 1 -factors to be （g,f） -uniform, f-uniform are given and the following result is proved： Let G be a graph with 1-factor F such that to（F）≥2 and to（F） -0 （mod 2）. Let g andfbe two integer-valued functions defined on V（G） such that g（x）≤f（x） for each vertex x of V（G）. Assume G-{x,y} be （g,f）-uniform for every component C =xy of F, then G is （g,f）-uniform. Furthermore, it has been shown that the conditions in the theorem are best possible in some sense.