徐蘭,蘇貴福

(1.昌吉學(xué)院數(shù)學(xué)系,新疆昌吉831100;2.北京化工大學(xué)理學(xué)院,北京100029)

1 引言

本文討論的圖都是有限,無向簡單連通圖.設(shè)G=(V(G),E(G))是一個(gè)簡單連通圖,用dG(v)和NG(v)分別表示頂點(diǎn)v∈V(G)在圖G中的度和鄰點(diǎn)集,而?(G)和δ(G)表示圖G的最大度和最小度.對任一非空子集S?V(G),用G[S]表示由S導(dǎo)出的子圖,用G?S表示刪除S中的點(diǎn)以及與其相關(guān)聯(lián)的邊后所得的圖.對圖G中的兩個(gè)不相交的頂點(diǎn)集S和T,用eG(S,T)表示連接S和T的邊數(shù).設(shè)X∈V(G)是一個(gè)非空集合,用NG(X)表示X中的所有頂點(diǎn)構(gòu)成的集合.

圖G的聯(lián)結(jié)數(shù)定義為

本文未加說明的符號和定義參看文獻(xiàn)[1].

圖的因子問題是近年來圖論研究的主要問題之一,其中圖的[a,b]-因子倍受研究者的青睞,它在網(wǎng)絡(luò)和計(jì)算機(jī)科學(xué)中有著廣泛的應(yīng)用.設(shè)a,b(a≤b)是兩非負(fù)整數(shù),G是一簡單連通圖,稱圖G的一個(gè)支撐子圖H為它的一個(gè)[a,b]-因子,如果對任意的頂點(diǎn)x∈V(G),都有a≤dH(x)≤b成立.特別地,當(dāng)a=b=k時(shí),[a,b]-因子就是圖的k-因子,關(guān)于圖的k-因子的結(jié)果可參閱[2].1990年Heinrich等人在文獻(xiàn)[3]中給出了圖中存在[a,b]-因子的充要條件.

定理1[4]設(shè)G是一個(gè)階數(shù)為的簡單圖,其中a,b是非負(fù)整數(shù),且1≤a≤b.若b(G)>則圖G中存在一個(gè)[a,b]-因子.

定理2[5]設(shè)a,b是非負(fù)整數(shù),1≤a≤b,H是圖G的子圖.那么G中存在[a,b]-因子F使得E(H)?E(F),當(dāng)且僅當(dāng)對V(G)的任意兩個(gè)不相交的子集S和T,有

后來的研究者通過圖的各種參數(shù)刻畫圖中存在[a,b]-因子的條件,詳細(xì)可參閱文獻(xiàn)[6-10].文章通過圖的聯(lián)結(jié)數(shù)刻畫了其中存在[a,b]-因子的一個(gè)充分條件.

2 主要結(jié)果

引理1[6]設(shè)G是一個(gè)簡單圖,a,b是非負(fù)整數(shù),a≤b,那么G中存在一個(gè)[a,b]-因子當(dāng)且僅當(dāng)對任意兩個(gè)不相交的頂點(diǎn)集S和T,有

定理3 設(shè)G是一個(gè)階數(shù)為的簡單圖,其中a,b是非負(fù)整數(shù),且1≤a≤b.若b(G)>則圖G中存在一個(gè)[a,b]-因子.

證明 根據(jù)引理1,只需證明δG(S,T)=b|S|+dG?S(T)?a|T|≥0即可.不失一般性,我們總假設(shè).因?yàn)槿鬞=?,則δG(S,T)=b|S|≥0.

為討論方便,以下分兩種情形證明.

情形1 對任意x∈T,有dG?S(x)≥a.此時(shí)δ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.首先證明這是因?yàn)橐虼擞?/p>

令p=|x:x∈T,dG?S(x)=0|,而Y=V(G)?S.由h=0知NG根據(jù)聯(lián)結(jié)數(shù)的定義,有

于是

根據(jù)上式,|S|+|T|≤n,得到

情形2.2 1≤h≤a?1.

如果存在點(diǎn)x1∈T,使得dG?S(x1)=h.令Y=(V(G)?S)?NG?S(x1),顯然x1∈Y?NG(Y).因此根據(jù)聯(lián)結(jié)數(shù)的定義,有

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

結(jié)合|S|+|T|≤n,有

因此

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

不難發(fā)現(xiàn),由定理3可推出定理1,亦即定理3的結(jié)果比定理1更好.