王仲梅，孟獻青，

（1．湖南商學(xué)院信息學(xué)院，湖南長沙 410205；2．山西大同大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，山西大同 037009）

本文僅考慮簡單有限無向圖.對度因子的研究是圖論的重要分支之一.Dirac[1]證明:若G是一個階n≥3的圖，且最小度，則G為Hamilton圖.以此定理為基礎(chǔ)引出了多種與度有關(guān)的問題的研究，給出了一個不同于文[2]中二部圖至少含k個圈的條件.在文中我們有如下記號:

引理1[2]設(shè)P=x1x2…xp是G中的一條路，其中x1∈V1，P=2r+d，d=0 或 d=1. 設(shè) y∈V2∩（V（G）－V（P）），如果dp（x1）+dp（xy）≥r+1），則G有一條路P*,使得 V（P*）=V（P）∪｛y｝.

引理2[4]設(shè)t＞s是兩個正整數(shù)，C是G中長為2t的圈，且w∈G－V（C）.如果則C+w包含一個圈C*，使得2s≤l（C*）＜2t.

引理3[4]設(shè)s≥3是一個正整數(shù)，C是G中長為2s的圈.設(shè)

如果dC（x）+dC（y）≥2s－1，則C中存在兩個頂點u∈V1和v∈V2，使得C－u+x包含一個長為2s的圈，且uy∈E（G）以及C－v+y包含一個長為2s的圈，且vx∈E（G）.

引理4[5]設(shè)C是G中的一個圈，P是G中的一條uv－路，其中 u∈V1且v∈V2，使得 V（C）∩V（P）=?.設(shè)l（C）=2q，如果dC（u）+dC（v）≥q+1，則G包含一個圈 C*，使得 V（C*）=V（C）∪V（P）．

引理 5 設(shè) s≥3是一個正整數(shù)，G=（V1，V2）是一個均衡二部圖，滿足如果G包含k個頂點不交的長至少為2s的圈，則包含一條Hamilton路.

證明 在G中選擇k個頂點不交的長至少為2s的圈 C1，C2，…，Ck．使得中的最長路盡可能的長.令設(shè),如果d=0，則結(jié)論顯然成立.下面假設(shè) d≥1.

設(shè)l（Ci）=2ni，對所有的i∈｛1，2，…，k｝，顯然由題設(shè)知ni≥s,且．不失一般性，設(shè)P=x1x2…xp是G1中的一條最長路，其中x1∈V1，P=2r+δ，δ=0 或 δ=1.

為了證明引理的結(jié)果我們用反證法.假設(shè)G1中不含 Hamilton 路，從而P＜2d.令 G2=G1－V（P），且u∈G2∩V2.因P是G1中的最長路，由引理1知dp（x1）+dp（u）≤r，又x1?G2，故dG2（x1）=0.而故dG2（u）≤d－r.因x1∈V1，u∈V2，得

從而在H中存在一個圈Ci，使得

因為ni≥s，故有dci（x1）+dci（u）≥2s－1＞s+1.由引理2及Ci的最小性可知l（Ci）=2s,根據(jù)引理3，可知存在點x0∈V（Ci）∩V2，使得C′i=Ci－x0+u包含一個長至少為 2s的圈，且 x0x1∈E（G）.用 C′i替換 Ci，我們得到Ci中的一條路P′=x0x1…xp.這與最長路P的選擇矛盾.從而p=2d，故G中存在一條Hamilton路.

定理1 設(shè)s≥3，G（V1，V2）是一個均衡二部圖,滿足+1.如果G包含k個頂點不交的長至少為2s的圈,則有一個至少包含k個頂點不交的長至少為2s的圈的 2－因子.

證明:設(shè)t是最大的整數(shù),使得G有t個長至少為2s的頂點不交的圈,滿足包含一條Hamilton路.也就是說我們選擇的長至少為2s的頂點不交的 t個圈，C1，C2，…，Ct，使得最大,由引理5知,t≥k.設(shè)l（Ci）=2ni，對所有的i∈｛1,2,…,t｝.顯然 ni≥s，令

設(shè)p=x1x2…x2d是G1中的一條Hamilton路,由的最大性及引理4知dGi（x1）+dGi（x2d）≤ni,對所有的 i∈｛1，2,…，t｝,故有

因為 ni≥s，且 t≥k≥2,d≥1,則有

從而有dG1（x1）≥s,或dG1（x2d）≥s.顯然在G1中存在一個長至少為2s的圈,這與t的最大性矛盾,故有即定理得證.

[1]Dirac G.Some theorems on abstract graphs[J].Proc London Math Soc,1952,2:69-81.

[2]Yan Jin,Liu Guizhen.On 2-factors with large cycles in a balanced bipartitegraph[J].Chinese Journal of Engineering Mathematics,2004,21(6):910-914.

[3]Bondy J A,Murty U S R.Graph Theory with Applications[M].New York:American Elsevier,1976.

[4]Wang H.Larg Vertex-disjoint cycles in bipartite graph[J].Graph Comb,2000,16:359-366.

[5]Wang H.On 2-factors of a bipartite Graph[J].Graph Theory,1999,31:101-106.