偶圖中相互獨立的4-圈和6-圈

魯富榮

（山西大學商務學院基礎教學部，山西太原 030031）

偶圖中相互獨立的4-圈和6-圈

魯富榮

（山西大學商務學院基礎教學部，山西太原 030031）

設k≥3是一個正整數,G=(X,Y;E)是一個頂點數為4k的偶圖,且有|X|=|Y|=2k。設δ(G)≥k+1,則圖G包含k-3個4-圈,1個6-圈和一條含6個頂點的路,且它們是相互獨立的。

偶圖；生成子圖；圈

本文考慮有限無向簡單圖,設G=(X,Y;E)是一個均衡偶圖,也即頂點數|X|=|Y|,其邊數E(G)=|E|。對于圖G的兩個子圖G1,G2,我們用E(G1,G2)表示一個頂點在圖G1,另一個頂點在圖G2中的邊集,令e(G1,G2)=|E(G1,G2)|。d(x)表示圖G中與點x相鄰的頂點數,稱d(x)為點x在圖G的度。設x和G′是圖G的頂點和子圖,d(x,G′)表示G′中與點x相鄰的頂點數,稱δ(G)=min{d(x)|x∈V(G)} 為圖G的最小度。若圖G的子圖集合中任何兩個子圖在G中沒有公共頂點,則稱此子圖集合是相互獨立的。以X為頂點集,以兩端點均在X中的G的邊的全體為邊集所組成的子圖,稱為G的由X導出的子圖,記為G[X]。若G′的頂點與圖G頂點相同，且G′的邊是圖G中的邊,則稱G′為圖G的生成子圖。其余未給出說明的記號可參照文獻[1]。

Zahar[2]給出了如下結論：若G的頂點數|G|=n1+n2,且,則G包含兩個長度分別為n1,n2的相互獨立的圈C1,C2。Zahar同時也作出了如下猜想：若G的頂點數n=n1+n2+…+nk且滿足,則G包含k個相互獨立的長度分別為n1,n2,…,nk的圈。此猜想目前尚未得到證明。

包含k個頂點的圈稱為k-圈．Erd和Faudree[3]猜想如果G是頂點數為4k的圖,并且δ(G)≥2k,則G包含k個相互獨立的4-圈。Wang又證明了如下結論：

引理1 一個頂點數為|X|=|Y|=2k偶圖,若δ(G)≥k+1,則圖G包含k-1個頂點不相交的4-圈和一條含4個頂點的路,且它們是相互獨立的。

同時Wang猜想一個頂點數為|X|=|Y|=2k偶圖,若δ(G)≥k+1,則圖G包含k個頂點不相交的4-圈。

基于上述結論，本文主要證明了如下的結果：

定理1設G=(X,Y;E)是頂點數為4k的偶圖,且有|X|=|Y|=2k,若δ(G)≥k+1,則圖G有一個生成子圖包含k-3個頂點不相交的4-圈,1個6-圈和一條含6個頂點的路,且它們是相互獨立的。

1 引理的證明

引理2設偶圖G有一條邊e=uv和一個4-圈Ci,且e和Ci相互獨立。若d(u,Ci)+d(v,Ci)≥3,則G[V(Ci)?{u,v}]包含一個6-圈。

證明假設圖G不包含一個6-圈,設Ci=x1x2x3x4x1,x1,x3∈X,x2,x4∈Y,且假設u∈Y,由已知條件d(u,Ci)+d(v,Ci)≥3,則d(u,Ci)≥1,不妨設u與x1相鄰,又因為d(u,Ci)≤2,則d(v,Ci)≥1，若v與x2或x4相鄰,則可得一個6-圈ux1xjx3xkvu,j≠k,{j,k}={2,4}。

引理3設偶圖G有兩個不相鄰頂點u,v和一個4-圈Ci,且u,v和Ci相互獨立。若d(u,Ci)+d(v,Ci)≥3,則G[V(Ci?{u,v})]包含一個含6個頂點的路。

證明設4-圈Ci=x1x2x3x4x1,x1,x3∈X,x2,x4∈Y,且假設u∈Y,由于d(u,Ci)+d(v,Ci)≥3,故有d(u,Ci)≥1,類似上述討論，不妨設u與x1相鄰,由于d(u,Ci)≤2,則有d(v,Ci)≥1,此時必有v與x2或x4相鄰,因此可得一個6-路ux1xjx3xkv,j≠k,{j,k}={2,4}。

2 定理的證明

定理2G=(X,Y;E)是頂點數為4k的偶圖,且有|X|=|Y|=2k,設δ(G)≥k+1,則圖G包含k-3個頂點不相交的4-圈,1個6-圈和一條含6個頂點的路,且它們相互獨立。

證明 由定理1可知,圖G包含k-1個頂點不相交的4-圈C1,C2,…,Ck-1和一條含4個頂點的路P。且設L=G[V(P)]。下面我們分情況來討論：

情形1：若L不包含4-圈,僅為4個頂點的路。令L=z1z2z3z4,z1,z3∈X,z2,z4∈Y,且z1z4?E(G),令H=G-L,則有,故在H中必存在圈Cj,使得e(L,Cj)≥5,此時在L中必存在兩個相鄰頂點z1,z2或z3,z4,使得d(zi,Cj)+d(zi+1,Cj)≥3,不妨設z1,z2滿足條件,由引理1可知G[V(L?Cj)]必包含一個6-圈和一條與之獨立的邊e=z3z4,另一情形類似可得結論。令H′=G-L-Cj,則有d(z3,H′)+d(z4,H′)≥2(k+1)-3-4=2(k-3)+1,故在H′中至少有一個頂點yi與z3或z4相鄰,而H′恰包含k-2個4-圈作為其生成子圖,設yi是其中某個4-圈Cl的頂點,則G[V(Cl?z3z4)]必包含一條含6個頂點的路。

情形2：當L恰為一個4-圈,也即圖G包含k個頂點不相交的4-圈令L=Ck=z1z2z3z4z1,z1,z3∈X,z2,z4∈Y,,則此時或存在圈Cj,使得e(Ck,Cj)≥5,或對任意圈Cj(j≠k)有e(Ck,Cj)=4。

情形3：若存在Cj使得e(Ck,Cj)≥5，此時必有z1,z2或z3,z4,使得d(zi,Cj)+d(zi+1,Cj)≥3,不妨設此時z1,z2滿足條件,則由引理1可知圖G[V(Ck?Cj)]必然包含一個6-圈C′和與之獨立的一條邊e=z3z4。此 時 令H′=G-Ck-Cj,則 有d(z3,H′)+d(z4,H′)≥2k+2-4-4=2(k-3)。

當k=3 時,δ(G)≥4,此時令C1=x1x2x3x4x1,C2=y1y2y3y4y1,x1,y1,x3,y3∈X,x2,y2,x4,y4∈Y,類似于上述討論可設e(C3,C2)≥5,則此時G[V(C3?C2)]必然包含一個6-圈C′和與之獨立的一條邊e=z3z4,若e({z3,z4},C1)≥1,則圖G[V(C1?z3z4)]包含一條有6個頂點的路,故我們只需考察當e({z3,z4},C1)=0的情形,又d(z3,C2)+d(z4,C2)≥8-4=4,故G[V(C2?z3z4)]包含一個6-圈,同理只需考慮e({z1,z2},C1)=0的情形,因此e(C1,C2)≥16-8=8,此時圖G必包含兩個6圈,因此只需考察k＞3的情形,而由上述討論可知d(z3,H′)+d(z4,H′)≥2(k-3)≥1,故在H′中至少有一個頂點yi與z3或z4相鄰,而H′恰包含k-2個4-圈作為其生成子圖,設yi是其中某個4-圈Cl的頂點,則G[V(Cl?z3z4)]必包含一條含6個頂點的路,結論得證。

情形4：若對于圖任何Cj(j≠k),均有e(Ck,Cj)=4,設Cj=v1v2v3v4v1,且有v2,v4∈X,v1,v3∈Y,由對稱性,故假設z1v1∈E(G),若d(z2,Cj)≥1,則 圖G[V(Ck?Cj)]必然包含一個6-圈C′和與之獨立的一條邊e=z3z4,類似情形3，討論可得結論。故我們只需考察d(z2,Cj)=0的情形,同理也可得d(z4,Cj)=0,此時必有z1v1,z1v3,z3v1,z3v3∈E(G),此時G[V(Ck?Cj)]包含6-圈y3v2v1z1z4z3v3及兩不相鄰頂點z2,v4,設H″=G-Ck-Cj,M=G[V(Ck?Cj)],則有d(z2,M)+d(y4,M)=4,故d(z2,H″)+d(y4,H″)≥ 2k+2-4=2(k-1)＞2(k-2),故在H″中存在 4-圈Ci,使得d(z2,Ci)+d(y4,Ci)≥3,由引理3可知G[V(Ci?{z2,y4})]包含一條有6個頂點的路。結論得證。

[1]Bondy J R,Murty U S R.Graph Theory with Applications[M].Amsterdam：North-Holland,1976.

[2]El-Zahar M H.On circuits in graphs[J].Discrete Math,1984,50：227-230.

[3]Erdo¨sP.Some recent combinatroial problems[M].Technical Report：University of Bielefeld,1990.

Abatract:Letk≥3be a positive integer．LetG=(X,Y;E)be a bipartite graph with|X|=|Y|=2k．Supposingδ(G)≥k+1,then G has a spanning subgraph consisting ofk-3quadrilaterals,one 6-cycle and a path of order 6 such that all of them are independent．

Disjoint 6-Cycles and 4-Cycles in Bipartite Graph

LU Fu-rong
（Basic Teaching Department，Business College of Shanxi University,Taiyuan Shanxi,030031）

bipartite graph；spanning graph;cycle

O157.5

A

1674-0874(2015)04-0017-02

2015-03-10

山西大學商務學院科研基金項目[2014030]

魯富榮（1981-）,男,山西河曲人，碩士,講師,研究方向：圖論。

〔責任編輯 高海〕