论文部分内容阅读
二十世纪六十年代以来,图论获得了空前发展,在物理学、化学、计算机科学等学科中得到了广泛应用。图的因子理论是图论的一个重要分支,也是图论研究中最活跃的课题之一。
本文考虑的图若无特殊声明均为简单、无向有限图,对于一个图G=G(V(G),E(G)),我们用V(G)和E(G)分别表示图的顶点集合和边集合。对任意的υ∈V(G),我们用dG(υ)表示顶点υ在G中的度数,NG(υ)表示在G中与υ相邻的点的集合,对任给的X∈V(G),定义NG(X)=Uχ∈XVG(x),G-X表示G中V(G)-X的导出子图,c(G-X)和o(C-X)分别表示G-X的连通分支数和奇分支数。我们用δ(G)和△(G)分别表示G中点的最小次数和最大次数。
设Z是整数的集合.Z+是非负整数的集合,设g和f是定义在V(G)上的两个整数值函数,即:g,f→Z+.如果存在G的一个支撑子图F,使得对任给的υ∈V(G),g(υ)≤dF(υ)≤f(υ),那么我们就称F是图G的一个(g,f)-因子。特别地,如果g(υ)=a,f(υ)=b.则F叫做G的一个[a,b]-因子。如果对任意的υ∈V(G),dF(υ)=f(υ),则F叫做G的一个f-因子。若g(x)=1,则F称为G的一个(1,f)-因子。若dF(υ)=k,则F叫做k因子。设G是一个图,f:V(G)→{1,3,5,...},如果H是G的一个子图,使得dH(X)∈{l,3,5…f(x)},则H叫做G的一个(1,f)-奇子图,若H是G的支撑了图,则H叫做G的一个(1,f)-奇因子。
设h是定义在图G的边集合E(G)上的一个函数,使对任意的e∈E(G),有h(e)∈[0,l]。对G中的任意顶点υ,令dhG(υ)=∑e∈Eυh(e),其中Eυ={e:e=υW∈E(G)},则称dhG(υ)是图G的顶点υ的分数度,若h满足对任意的v∈V(G),有g(υ)≤dhG(υ)max{1,n},δ(G)≥n+2,如果则G是(1,b,n)一可扩充图。