偶图中相互独立的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-）,男,山西河曲人，硕士,讲师,研究方向：图论。

〔责任编辑 高海〕