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

刘红霞; 方小娟

doi:10.13951/j.cnki.37-1213/n.2007.04.003

烟台大学学报（自然科学与工程版） ›› 2007, Vol. 20 ›› Issue (4) : 235 -239. DOI: 10.13951/j.cnki.37-1213/n.2007.04.003

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

刘红霞, 方小娟

作者信息 +

Author information +

文章历史 +

摘要

既是(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)-对等图.并指出定理中的条件在一定意义上是最好可能的.