路因子臨界覆蓋圖存在的若干充分條件

袁 園

(海南大學數學與統計學院,海南 ?？?570228)

在這篇文章中,我們主要考慮簡單圖. 本文未定義的概念和術語,讀者可以參考文獻[1].

設G是一個圖,其中頂點集是V(G),邊集是E(G).對于圖G的任一點v,用符號dG(v) 表示點v的度數.給定頂點子集S?V(G),G[S] 表示由S誘導的圖G的子圖.記G-S=G[V(G)S]且κ(G) 為圖G的連通度.通常,用ω(G) 和i(G) 分別表示圖G的連通分支和孤立點的個數.圖G的聯結數定義為:

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

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

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

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

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

1 預備知識

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

引理1[5]連通圖G是P≥2-因子覆蓋的當且僅當對于任意頂點子集X,成立

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

其中,ε1(X)定義為

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

引理2[2]連通圖G是P≥3-因子覆蓋的當且僅當對于任意頂點子集X成立

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

其中,ε2(X)定義為

2 定理3的證明

在本節,我們通過聯結數和連通度給出了P≥2-因子覆蓋圖存在的條件.

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

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

(1)

接下來根據 |X| 的值進行分類討論.

情形1|X|=0.

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

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

(2)

因為κ(G)≥k+r+1,所以i(L)=0,這與不等式(2)相矛盾.

情形21≤|X|≤r.

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

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

(3)

因為κ(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|.再根據不等式(4)和聯結數的定義可得

(5)

這顯然是一個矛盾.結論成立.

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

3 定理4的證明

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

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

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

(6)

對某個子集X?V(G) 成立.現在我們考慮下面的4種情形.

情形1|X|=0.

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

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

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

論斷L是一個大太陽.

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

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

情形21≤|X|≤r.

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

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

產生矛盾.

情形3|X|=r+1.

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

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

(7)

子情形3.1L-X有一個非太陽的分支Y.

子情形3.1.1a≥1.

令W=V(Y)∪V(aK1)∪V(bK2)∪V(T1)∪…∪V(Tc),其中a,b,c分別表示孤立點、K2和大太陽分支的個數,從而

且

根據聯結數的定義,我們可以得到

子情形3.1.2a=0.

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

因為

和

所以

子情形3.2L-X沒有非太陽分支.

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

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分別表示孤立點、K2以及大太陽分支的數目.結合聯結數的定義,可以得到

子情形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分別表示孤立點、K2以及大太陽分支的數目.

子情形4.1b+c=0.

在這種情形下,容易得到a≥2|X|-1.根據聯結數的定義,可以得到

子情形4.2b+c≥1.

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

根據聯結數的定義,下面的式子成立

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

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

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