徐兰,苏贵福

(1.昌吉学院数学系,新疆昌吉831100;2.北京化工大学理学院,北京100029)

1 引言

本文讨论的图都是有限,无向简单连通图.设G=(V(G),E(G))是一个简单连通图,用dG(v)和NG(v)分别表示顶点v∈V(G)在图G中的度和邻点集,而∆(G)和δ(G)表示图G的最大度和最小度.对任一非空子集S⊆V(G),用G[S]表示由S导出的子图,用G−S表示删除S中的点以及与其相关联的边后所得的图.对图G中的两个不相交的顶点集S和T,用eG(S,T)表示连接S和T的边数.设X∈V(G)是一个非空集合,用NG(X)表示X中的所有顶点构成的集合.

图G的联结数定义为

本文未加说明的符号和定义参看文献[1].

图的因子问题是近年来图论研究的主要问题之一,其中图的[a,b]-因子倍受研究者的青睐,它在网络和计算机科学中有着广泛的应用.设a,b(a≤b)是两非负整数,G是一简单连通图,称图G的一个支撑子图H为它的一个[a,b]-因子,如果对任意的顶点x∈V(G),都有a≤dH(x)≤b成立.特别地,当a=b=k时,[a,b]-因子就是图的k-因子,关于图的k-因子的结果可参阅[2].1990年Heinrich等人在文献[3]中给出了图中存在[a,b]-因子的充要条件.

定理1[4]设G是一个阶数为的简单图,其中a,b是非负整数,且1≤a≤b.若b(G)>则图G中存在一个[a,b]-因子.

定理2[5]设a,b是非负整数,1≤a≤b,H是图G的子图.那么G中存在[a,b]-因子F使得E(H)⊆E(F),当且仅当对V(G)的任意两个不相交的子集S和T,有

后来的研究者通过图的各种参数刻画图中存在[a,b]-因子的条件,详细可参阅文献[6-10].文章通过图的联结数刻画了其中存在[a,b]-因子的一个充分条件.

2 主要结果

引理1[6]设G是一个简单图,a,b是非负整数,a≤b,那么G中存在一个[a,b]-因子当且仅当对任意两个不相交的……