袁 園

(海南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,海南 ?？?570228)

在這篇文章中,我們主要考慮簡(jiǎn)單圖. 本文未定義的概念和術(shù)語(yǔ),讀者可以參考文獻(xiàn)[1].

設(shè)G是一個(gè)圖,其中頂點(diǎn)集是V(G),邊集是E(G).對(duì)于圖G的任一點(diǎn)v,用符號(hào)dG(v) 表示點(diǎn)v的度數(shù).給定頂點(diǎn)子集S?V(G),G[S] 表示由S誘導(dǎo)的圖G的子圖.記G-S=G[V(G)S]且κ(G) 為圖G的連通度.通常,用ω(G) 和i(G) 分別表示圖G的連通分支和孤立點(diǎn)的個(gè)數(shù).圖G的聯(lián)結(jié)數(shù)定義為:

記Pn為具有n個(gè)頂點(diǎn)的路.圖G的路因子是一個(gè)生成子圖,其中每個(gè)分支是階數(shù)至少為2的路.P≥t-因子是每個(gè)分支的階數(shù)t≥2 的路因子.設(shè)H是一個(gè)因子臨界圖,如果圖G=K1,或G=K2,或?qū)DH中的每個(gè)頂點(diǎn)u增加一個(gè)新的頂點(diǎn)v作成一條新的邊,那么稱(chēng)圖G是一個(gè)太陽(yáng)(sun). 具有至少6個(gè)頂點(diǎn)的太陽(yáng)稱(chēng)為大太陽(yáng)(big sun).用符號(hào) sun(G) 表示圖G的太陽(yáng)分支的數(shù)目.如果對(duì)于圖G的任意一條邊e,都存在一個(gè)P≥t-因子包含邊e,則稱(chēng)G是P≥t-因子覆蓋的.文獻(xiàn)[2]給出了 (P≥t,k)-因子臨界覆蓋圖的概念:對(duì)于圖G的任意子集S,|S|=k,如果G-S是P≥t-因子覆蓋的,則稱(chēng)圖G是 (P≥t,k)-因子臨界覆蓋的.

我們列出一些關(guān)于P≥t-因子的已知結(jié)果.文獻(xiàn)[3]給出了P≥2-因子存在的充分必要條件.文獻(xiàn)[4]刻畫(huà)了具有P≥3-因子的圖類(lèi).文獻(xiàn)[5]刻畫(huà)了P≥2-因子和P≥3-因子覆蓋圖.文獻(xiàn)[2]給出了 (P≥2,k)-因子臨界覆蓋圖和(P≥3,k)-因子臨界覆蓋圖存在的充分條件.關(guān)于因子的更多結(jié)果可參考文獻(xiàn)[6-9].

定理1[2]k≥0 是一個(gè)整數(shù),圖G滿(mǎn)足κ(G)≥k+1.若 bind(G)>k+1,則G是 (P≥2,k)-因子臨界覆蓋圖.

定理2[2]k≥1是一個(gè)整數(shù),圖G滿(mǎn)足κ(G)≥k+1,|V(G)|≥k+3.若bind(G)>k+2,則G是(P≥3,k)-因子臨界覆蓋圖.

圖G稱(chēng)為P≥k-因子一致圖,如果對(duì)任意邊e1,e2∈E(G),G中存在P≥k-因子覆蓋e1且避開(kāi)e2.最近,文獻(xiàn)[10]借助聯(lián)結(jié)數(shù)刻畫(huà)了P≥3-因子一致圖.受這些結(jié)果的啟發(fā),一個(gè)自然且有趣的想法是給出(P≥2,k)-因子臨界覆蓋圖和(P≥3,k)-因子臨界覆蓋圖的刻畫(huà).我們的主要結(jié)果是借助連通度和聯(lián)結(jié)數(shù)給出這兩類(lèi)圖存在的充分條件,從而推廣了文獻(xiàn)[2]中的結(jié)果.

1 預(yù)備知識(shí)

在本節(jié),為了給出主要結(jié)果的證明,需要用到下面的兩個(gè)引理.第一個(gè)引理得到了P≥2-因子覆蓋圖存在的充分必要條件.

引理1[5]連通圖G是P≥2-因子覆蓋的當(dāng)且僅當(dāng)對(duì)于任意頂點(diǎn)子集X,成立

i(G-X)≤2|X|-ε1(X),

其中,ε1(X)定義為

下面的引理給出了圖中存在P≥3-因子覆蓋圖的充分必要條件.

引理2[2]連通圖G是P≥3-因子覆蓋的當(dāng)且僅當(dāng)對(duì)于任意頂點(diǎn)子集X成立

sun(G-X)≤2|X|-ε2(X),

其中,ε2(X)定義為

2 定理3的證明

在本節(jié),我們通過(guò)聯(lián)結(jié)數(shù)和連通度給出了P≥2-因子覆蓋圖存在的條件.

如果r=0,由定理1可知定理3是成立的.接下來(lái)我們考慮r≥1.對(duì)任意子集S?V(G),|S|=k,令L=G-S.為了證明定理3,我們只需證明L是P≥2-因子覆蓋的.用反證法,假設(shè)L不是P≥2-因子覆蓋的.根據(jù)引理1,下面的式子成立

i(L-X)≥2|X|-ε1(X)+1.

(1)

接下來(lái)根據(jù) |X| 的值進(jìn)行分類(lèi)討論.

情形1|X|=0.

顯然,ε1(X)=0.根據(jù)不等式(1),我們可以得到

i(H-X)=i(H)≥1.

(2)

因?yàn)棣?G)≥k+r+1,所以i(L)=0,這與不等式(2)相矛盾.

情形21≤|X|≤r.

顯然地,ε1(X)≤|X|.根據(jù)不等式(1),我們可以得到

i(L-X)≥2|X|-ε1(X)+1≥|X|+1≥2.

(3)

因?yàn)棣?G)≥k+r+1,所以i(L-X)=0,這與不等式(3)相矛盾.

情形3|X|≥r+1.

注意到ε1(X)≤2,由不等式(1)可得

i(L-X)≥2|X|-1.

(4)

令E={x:dL-X(x)=0,x∈V(L)},由不等式(4)可得E≠φ且 |NG(E)|≤|S|+|X|=k+|X|.再根據(jù)不等式(4)和聯(lián)結(jié)數(shù)的定義可得

(5)

這顯然是一個(gè)矛盾.結(jié)論成立.

對(duì)任意S?V(Kk+r),|S|=k,令L=G-S.選擇X=V(Kk+r)S?V(L),因?yàn)閄不是獨(dú)立集,所以ε1(X)=2.從而,i(L-X)=2r-1>2r-2.根據(jù)引理1,L不是P≥2-因子覆蓋的,因此,G不是(P≥2,k)-因子臨界覆蓋的.

3 定理4的證明

當(dāng)r=0,根據(jù)定理2,可知G是 (P≥3,k)-因子臨界覆蓋的.因此,我們只需要考慮r≥1 的情形.

對(duì)任意S?V(G),|S|=k,令L=G-S.為了證明定理4,接下來(lái)證明L是P≥3-因子覆蓋的.用反證法.假設(shè)L不是P≥3-因子覆蓋的.根據(jù)引理2,可以得到

sun(H-X)≥2|X|-ε2(X)+1

(6)

對(duì)某個(gè)子集X?V(G) 成立.現(xiàn)在我們考慮下面的4種情形.

情形1|X|=0.

在這種情形下,ε2(X)=0.借助不等式(6),下面的式子成立

1≤sun(L-X)=sun(L)≤ω(L)=1,

這意味著 sun(L)=ω(L)=1.

論斷L是一個(gè)大太陽(yáng).

否則,L=K1或L=K2.從而|V(G)|=|S|+|V(L)|≤2+k,這與 |V(G)|≥k+3 相矛盾.

根據(jù)上面的論斷,記F是L的因子臨界圖,則有 |V(L)V(F)|=|V(F)|≥3,從而可以得到

情形21≤|X|≤r.

顯然,ε2(X)≤|X|.根據(jù)不等式(6),我們可以得到

1=ω(L-X)≥sun(L-X)≥2|X|-ε2(X)+1≥2,

產(chǎn)生矛盾.

情形3|X|=r+1.

在這種情形下,ε2(X)≤2.根據(jù)不等式(6),可以得到

sun(L-X)≥2|X|-ε2(X)+1≥2r+1.

(7)

子情形3.1L-X有一個(gè)非太陽(yáng)的分支Y.

子情形3.1.1a≥1.

令W=V(Y)∪V(aK1)∪V(bK2)∪V(T1)∪…∪V(Tc),其中a,b,c分別表示孤立點(diǎn)、K2和大太陽(yáng)分支的個(gè)數(shù),從而

且

根據(jù)聯(lián)結(jié)數(shù)的定義,我們可以得到

子情形3.1.2a=0.

令M=V(Y)∪V(bK2)∪V(T1)∪…∪V(Tc),其中a,b,c分別表示孤立點(diǎn)、K2和大太陽(yáng)分支的個(gè)數(shù),則存在點(diǎn)x,y∈V(M) 滿(mǎn)足dM(x)=1,xy∈E(M).

因?yàn)?/p>

和

所以

子情形3.2L-X沒(méi)有非太陽(yáng)分支.

在這種情形下,我們可以得到

sun(L-X)=a+b+c≥2|X|-ε2(X)+1≥2r+1.

子情形3.2.1a≥1.

令P=ak1∪bK2∪T1∪T2∪…∪Tc,其中a,b,c分別表示孤立點(diǎn)、K2以及大太陽(yáng)分支的數(shù)目.結(jié)合聯(lián)結(jié)數(shù)的定義,可以得到

子情形3.2.2a=0.

從而得到

這與條件

(kr+r+k+1)(4r+1)-(2r+1)(k+r+1)=2r2+2kr+4kr2+2r>0相矛盾.

情形4|X|≥r+2.

顯然地,ε2(X)≤2.借助不等式(6),我們可以得到

sun(L-X)=a+b+c≥2|X|-ε2(X)+1≥2|X|-1.

(8)

令a,b,c分別表示孤立點(diǎn)、K2以及大太陽(yáng)分支的數(shù)目.

子情形4.1b+c=0.

在這種情形下,容易得到a≥2|X|-1.根據(jù)聯(lián)結(jié)數(shù)的定義,可以得到

子情形4.2b+c≥1.

令P=(bK2)∪V(T1)∪…∪V(Tc).則存在兩個(gè)頂點(diǎn)x,y∈V(P) 滿(mǎn)足dP(x)=1,xy∈E(P).

根據(jù)聯(lián)結(jié)數(shù)的定義,下面的式子成立

注3條件κ(G)≥k+r+1 不能用κ(G)≥k+r替換.

sun(L-X)=2r-1>2|X|-ε2(X)=2r-2.

通過(guò)引理2,L不是P≥3-因子覆蓋的.因此G不是 (P≥3,k)-因子臨界覆蓋的.