图中存在[a,b]-因子的一个充分条件∗

徐兰,苏贵福

(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]-因子当且仅当对任意两个不相交的顶点集S和T,有

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

证明 根据引理1,只需证明δG(S,T)=b|S|+dG−S(T)−a|T|≥0即可.不失一般性,我们总假设.因为若T=∅,则δG(S,T)=b|S|≥0.

为讨论方便,以下分两种情形证明.

情形1 对任意x∈T,有dG−S(x)≥a.此时δG(S,T)=b|S|+dG−S(T)−a|T|≥b|S|+a|T|−a|T|≥0.

情形2存在x∈T,使得dG−S(x)≤a−1.

令h=min{dG−S(x):x∈T}.显然1≤h≤(a−1).我们分两种情形加以说明.

情形2.1h=0.首先证明这是因为因此有

令p=|x:x∈T,dG−S(x)=0|,而Y=V(G)−S.由h=0知NG根据联结数的定义,有

于是

根据上式,|S|+|T|≤n,得到

情形2.2 1≤h≤a−1.

如果存在点x1∈T,使得dG−S(x1)=h.令Y=(V(G)−S)−NG−S(x1),显然x1∈Y−NG(Y).因此根据联结数的定义,有

于是n−1≥|NG(Y)|≥bind(G)|Y|=bind(G)(n−h−|S|).即

结合|S|+|T|≤n,有

因此

注意到δG(S,T)是整数,于是δG(S,T)≥0.

不难发现,由定理3可推出定理1,亦即定理3的结果比定理1更好.