偶圖中相互獨(dú)立的4-圈和6-圈

魯富榮

（山西大學(xué)商務(wù)學(xué)院基礎(chǔ)教學(xué)部，山西太原 030031）

偶圖中相互獨(dú)立的4-圈和6-圈

魯富榮

（山西大學(xué)商務(wù)學(xué)院基礎(chǔ)教學(xué)部，山西太原 030031）

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

偶圖；生成子圖；圈

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

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

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

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

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

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

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

1 引理的證明

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

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

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

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

2 定理的證明

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

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

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

情形2：當(dāng)L恰為一個(gè)4-圈,也即圖G包含k個(gè)頂點(diǎn)不相交的4-圈令L=Ck=z1z2z3z4z1,z1,z3∈X,z2,z4∈Y,,則此時(shí)或存在圈Cj,使得e(Ck,Cj)≥5,或?qū)θ我馊j(j≠k)有e(Ck,Cj)=4。

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

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

情形4：若對(duì)于圖任何Cj(j≠k),均有e(Ck,Cj)=4,設(shè)Cj=v1v2v3v4v1,且有v2,v4∈X,v1,v3∈Y,由對(duì)稱性,故假設(shè)z1v1∈E(G),若d(z2,Cj)≥1,則 圖G[V(Ck?Cj)]必然包含一個(gè)6-圈C′和與之獨(dú)立的一條邊e=z3z4,類似情形3，討論可得結(jié)論。故我們只需考察d(z2,Cj)=0的情形,同理也可得d(z4,Cj)=0,此時(shí)必有z1v1,z1v3,z3v1,z3v3∈E(G),此時(shí)G[V(Ck?Cj)]包含6-圈y3v2v1z1z4z3v3及兩不相鄰頂點(diǎn)z2,v4,設(shè)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個(gè)頂點(diǎn)的路。結(jié)論得證。

[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

山西大學(xué)商務(wù)學(xué)院科研基金項(xiàng)目[2014030]

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

〔責(zé)任編輯 高海〕