在1-連通和2-連通的二部圖中保持連通度的一些樹的研究?

羅蓮，田應智

(新疆大學 數學與系統科學學院，新疆 烏魯木齊 830017)

0 引言

本文只考慮無自環和無平行邊的有限無向圖.V(G),E(G) 和δ(G) 分別表示的是圖G 的點集,邊集和最小度.圖G 的階|G|表示的是它的點集的基數.對于任意的點v ∈V(G),N(v)=NG(v)表示與點v 相鄰的所有的頂點的集合,并且dG(v)=|NG(v)| 稱為圖G 中點v 的度數.一個樹T 中度為1 的點稱之為樹T 的葉子,Leaf(T)表示的是樹T 的葉子點的集合.一個樹T 中度數至少為2 的點稱之為樹T 的內點,VI(T)表示的是樹T 的內點的集合.對于任意的一個非空子集S ?V(G),G[S] 表示的是由S 導出G 的子圖.圖G 的連通度記作κ(G),是滿足G-S 是不連通的或是平凡圖K1的最小點集S 的基數.如果κ(G)≥k,則稱G 是k-連通的.若B 是G 的一個極大的沒有割點的連通子圖,則稱B 是G 的塊.本文中未定義的術語和符號可參閱文獻[1].

Chartrand 等人給出如下著名定理.

定理1[2]任意連通圖G 中存在點x,使得G-x 仍然是k-連通的.Fujita 和Kawarabayashi 在[3] 中驗證了的k-連通的圖G 中存在相鄰的兩點u,v 使得G-{u,v} 仍然是k-連通的.他們也提出如下猜想.

猜想1[3]對任意的正整數k,m,存在一個非負整數fk(m) 使得的k-連通圖G 中存在一個階為m 的連通子圖W,使得G-W 仍然是k-連通的.

他們還在[3] 中驗證了對任意的正整數k,m,都有fk(m) ≥m.Mader 在[4] 中驗證了猜想1 中的參數fk(m)=m,并且可取連通子圖W 為一條路P.

定理2[4]對任意的正整數k,m,每一個的k-連通圖G 中存在一個階為m 的路P,使得G-V(P) 仍然是k-連通的.

基于定理2,Mader 提出如下猜想.

猜想2[4]對任意的階為m 的樹T,每一個的k-連通圖G 中存在一個子樹T′～=T,使得G-V(T′) 仍然是k-連通的.

在[5] 中,Mader 證明了δ(G)≥2(k-1+m)2+m-1 時,猜想2 是成立的.

定理3[5]對任意的階為m 的樹T,每一個δ(G)≥2(k-1+m)2+m-1 的k-連通圖G 中存在一個子樹T′～=T,使得G-V(T′) 仍然是k-連通的.

Diwan 和Tholiya 在[6] 中驗證了猜想2 在k=1 時的情形.

定理4[6]對任意的階為m 的樹T,每一個δ(G)≥m 的連通圖G 中存在一個子樹T′～=T,使得G-V(T′)仍然是連通的.

對于猜想2,當k=2 時,Tian 等學者在[7-8]中驗證了T 是星圖,雙星圖,或路雙星圖時的情形;Hasunuma和Ono 在[9] 中驗證了當T 有至多5 個內點,或者T 是一個擬單調的毛毛蟲圖或是一個具有6 個內點的毛毛蟲圖的情形;在[10] 中Lu 等學者驗證了當T 的直徑至多是4 的情形;在[11] 中Hong 等學者驗證了當T 是任意的毛毛蟲圖和蜘蛛圖時的情形.關于二部圖的點連通度的其他研究可參閱文獻[12-13].

受到以上結論的啟發,我們也對二部圖提出了類似的猜想.

猜想3對任意的具有二部劃分X 和Y 的樹T,每一個δ(G)≥k+t (t=max{|X|,|Y|})的k-連通的二部圖G 中存在一個子樹T′～=T,使得G-V(T′) 仍然是k-連通的.

把T 中最多有一個點的度大于1 的樹稱為星圖.把T 中只有兩個相鄰點的度大于或等于2 的樹稱為雙星圖.對于樹T,若VI(T)/=?且T[VI(T)] 是一條路P,則T 是一個毛毛蟲圖.可以看出星圖和雙星圖都是特殊的毛毛蟲圖.

在本文中,我們驗證了猜想3 在k=1 和k=2 時,T 是一個內點的個數至多為3 的毛毛蟲圖的情形是對的.

1 主要結果

在這一節中,我們首先給出一些在二部圖中子樹存在的度條件的結論.

由引理1,我們可以得到下面的推論.

推論1設T 是一個具有二部劃分X 和Y 的樹,記t=max{|X|,|Y|},每一個δ(G)≥t 的二部圖G 中存在一個子樹T′～=T.

下面我們將要證明主要結論.

定理5 設T 是一個具有二部劃分X 和Y 的樹,記t=max{|X|,|Y|}.如果T 的內點的個數不大于3,則每一個δ(G)≥t+1 的連通的二部圖G 中存在一個子樹T′～=T 使得G-V(T′) 仍然是連通的.

證明假設此定理是不成立的.由推論2 知G 中存在與T 同構的子樹T′.在所有同構于T 的子樹中,選擇一個子樹T′使得G-V(T′)包含的連通子圖的階數最大.設H0是G-V(T′)的最大連通分支,H1=G-V(T′∪H0),由假設知V(H1)/=?.

因為G 是連通的,所以存在v ∈V(T′) 使得N(v)∩V(H0)/=?.又因為δ(G)≥t+1,所以對任意的h ∈H1都有即δ(G[V(H1)])≥1.

當毛毛蟲圖T 的內點的個數為1 時,T 同構于星圖.對任意的h ∈H1,|N(h)∩V(G-(V(H0)∪{v}))|≥t+1-1=t.由推論1 知,我們可以在G-(V(H0)∪{v}) 中找到一個以點h 為中心點的星圖T′′～=T.但是V(H0)∪{v} 包含在G-V(T′′) 的一個連通分支中,這與T′的選擇矛盾.

當毛毛蟲圖T 的內點的個數為2 時,T 同構于雙星圖.由于δ(G[V(H1)]) ≥1,則H1中至少存在一邊e=h1h2.因為|N(h1)∩V(G-(V(H0)∪{v}))|≥t 和|N(h2)∩V(G-(V(H0)∪{v}))|≥t,那么由引理1 知,在G-(V(H0)∪{v}) 中存在一個以邊e=h1h2的點為中心點的雙星圖T′′～=T.但是V(H0)∪{v} 包含在G-V(T′′)的一個連通分支中,這與T′的選擇矛盾.

現在來看當毛毛蟲圖T 的內點的個數為3 時的情形.若H1中存在一條長為2 的路P=h1h2h3,因為|N(h1)∩V(G-(V(H0)∪{v}))|≥t,|N(h2)∩V(G-(V(H0)∪{v}))|≥t 和|N(h3)∩V(G-(V(H0)∪{v}))|≥t,所以由引理1 知,在G-(V(H0)∪{v})中存在一個以路P=h1h2h3的點為中心點的毛毛蟲圖T′′～=T.但是V(H0)∪{v}包含在G-V(T′′) 的一個連通分支中,這與T′的選擇矛盾.因此H1中的連通分支都同構于K2.對任意的邊h1h2∈H1,因為δ(G)≥t+1,所以|N(h1)∩V(T′)|=t,|N(h2)∩V(T′)|=t.設T′的二部劃分為X′和Y′.不妨假設h1和Y′中的點都相連,h2和X′中的點都相連.如果v ∈X′,那么我們用h1代替v 可以找到一個毛毛蟲圖T′′～=T.但這時V(H0)∪{v} 包含在G-V(T′′) 的一個連通分支中,這與T′的選擇矛盾.如果v ∈Y′,那么我們用h2代替v 可以找到一個毛毛蟲圖T′′～=T.但這時V(H0)∪{v} 包含在G-V(T′′) 的一個連通分支中,這也與T′的選擇矛盾.

綜上可知,假設不成立,則定理5 的結論是正確的.

定理6設T 是一個具有二部劃分X 和Y 的毛毛蟲圖,記t=max{|X|,|Y|}.如果T 的內點的個數不大于3,則每一個δ(G)≥t+2 的2-連通的二部圖G 中存在一個子樹T′～=T 使得G-V(T′) 仍然是連通的.

證明假設此定理是不成立的.由二部圖中子樹存在的度條件知,G 中存在與T 同構的子樹T′.在所有同構于T 的子樹中,選擇一個子樹T′使得G-V(T′) 中包含的塊的階數最大,記G-V(T′) 中階數最大的塊為B.因為δ(G-V(T′))≥2,所以|B|≥3 且B 是2-連通的.除此之外,因為G-V(T′) 不是2-連通的,所以G-V(T′∪B)/=?.令H=G-V(T′∪B).通過對B 的假設知,對任意的h ∈H,都有|N(h)∩V(B)| ≤1 和|N(h)∩V(H)|≥t+2-|N(h)∩V(B)|-|N(h)∩V(T′)|≥t+2-1-t=1,即δ(G[V(H)])≥1.

論斷1對任意的v ∈T′,|N(v)∩V(B)|≤1.

假設論斷1 不成立,那么存在v ∈T′,使得|N(v)∩V(B)|≥2.

當毛毛蟲圖T 的內點的個數為1 時,T 同構于星圖.因為對于任意的h ∈H,|N(h)(V(B)∪{v})|≥t+2-1-1=t,所以我們可以很容易地在G-(V(B)∪{v}) 中找到一個以h 為中心點的同構于T 的星圖T′′.但是V(B)∪{v}包含在G-V(T′′) 的一個塊中,這與假設矛盾.

當毛毛蟲圖T 的內點的個數為2 時,T 同構于雙星圖.由于δ(G[V(H)])≥1,則H 中至少存在一邊e=h1h2.因為|N(h1)∩V(G-(V(B)∪{v}))|≥t 和|N(h2)∩V(G-(V(B)∪{v}))|≥t,那么由引理1 知,在G-(V(B)∪{v})中存在一個以邊e=h1h2的點為中心點的雙星圖T′′～=T.但是V(B)∪{v} 包含在G-V(T′′) 的一個塊中,這與假設矛盾.

現在來看當毛毛蟲圖T 的內點的個數為3 時的情形.若H1中存在一條長為2 的路P=h1h2h3,因為|N(h1)∩V(G-(V(B)∪{v}))|≥t,|N(h2)∩V(G-(V(B)∪{v}))|≥t 和|N(h3)∩V(G-(V(B)∪{v}))|≥t,所以由引理1 知,在G-(V(B)∪{v}) 中存在一個以路P=h1h2h3的點為中心點的毛毛蟲圖T′′～=T.但是V(B)∪{v}包含在G-V(T′′) 的一個塊中,這與假設矛盾.因此H 中的連通分支都同構于K2.對任意的邊h1h2∈H,因為δ(G)≥t+2,所以|N(h1)∩V(T′)|≥t,|N(h2)∩V(T′)|≥t.設T′的二部劃分為X′和Y′.不妨假設h1和Y′中的點都相連,h2和X′中的點都相連.如果v ∈X′,那么我們用h1代替v 可以找到一個毛毛蟲圖T′′～=T.但這時V(B)∪{v} 包含在G-V(T′′) 的一個塊中,這與T′的選擇矛盾.如果v ∈Y′,那么我們用h2代替v 可以找到一個毛毛蟲圖T′′～=T.但這時V(B)∪{v} 包含在G-V(T′′) 的一個塊中,這又與T′的選擇矛盾.

綜上所述,論斷1 是正確的.

因為G 是2-連通的,所以在G 中存在一個最短的路P=p1,p2,···,pr?1,pr,其中p1,pr∈V(B)且pi∈V(T′∪H)(2 ≤i ≤r-1).因為對于任意的點v ∈V(T′∪H) 都有|NG(v)∩V(B)|≤1,那么|P|≥4.又因為P 是最短路,所以NG(p2)∩V(B ∪P)={p1,p3},那么|NG(p2)∩V(H ∪T′)|=dG(p2)-|NG(p2)∩V(B ∪P)|≥t+2-2=t,這意味著V(G)V(B ∪P)/=?.而對于任意的s ∈V(G)V(B ∪P),一定有|NG(s)V(B ∪P)|=dG(s)-|NG(s)∩V(B ∪P)|≥t+2-2=t (二部圖中同一條邊上的點的鄰點集合不會相交).因此由推論2 可知,G-V(B∪P) 中存在一個子樹T′′～=T,然而V(B)∪V(P) 包含在G-V(T′′) 的一個塊中,這與T′的選擇矛盾.

綜上可知,假設不成立,則定理6 的結論是正確的.