关于Ore-(1)型图中的Hamilton圈.pdf_大学文库

献〔1〕。关于Hamilton圈的研究已有很多结果，但关于边不交的Hamilton圈的研究却不算多。刘振宏r3)证明了偶数阶Ore-(2)型图有两个边不交的Hamilton圈。本文作者c4)证明了偶数阶Ore-(3)型图有边不交的两个Hamilton圈和一个1-因子。最近本文作者之一c5)证明了： n阶(n≥40)Ore-(-1)型图G(6(G)≥7)有两个边不交的Hami1ton圈除了3类图外。 Win()证明了偶数阶Ore-(1)型图有边不交的-一个Hami1ton圈和一个1-因子。本文将证明： 2n阶(n≥13)Ore-(1)型图G(6(G)≥7)有边不交的两个Hamilton圈和-一个1-因子。 1引理为了证明本文的主要定理，先介绍一些引理。引理1e)设G是具有a(G)≤6(G)的简单图，u,v∈V(G)且uvEE(G)。令Bo(u,v)= V(G)川-d(u)-d(v),R&(u,v)={s∈Rc(u,v):d(x)≥0e(u,v)+2}。如果|R6(u,o)川 0a(u,v),或者|R&(u,v)月=9c(4,o)且.r(G)≥2，则G是Hamilton图当且仅当G+uv是n Homiiton图。引理2：8)设G是具有a(G)≤(G)且k(G)1的简单图，u,v∈v(G)且uv∈E(G)。如果d(u)+d(w)≥IV(G川-(k(G)-1),那么G是Hamilton图当且仅当G+uv是Hamilt o 图。图G在引理1和2下的闭包仍用G表示。引理3设G是2n阶Ore-(1)型图，令X={x:d(x)≤n,￥∈V(G)》,则X1≤n-1 引理3证明是比较简单的，略证。引理4设G是2n(n≥13)阶Ore-(1)型图且6(G)≥7，则G具有边不交的一个Hamilton 圈H和一个1-因子N使得k(G-H-N)≥2 证明：显然G中含有边不交的一个Hamilton圈H和一个1-因子N。令G'=G-H-N, H1=G-H,H2=G-N,X={x:x∈V(G),d()≤m},Y=V(G)-X。由引理8可知 X1≤n-1。如果G'是2-连通，则引理成立。因此设G'不是2-连通。下面分两种情形来证明。 (1)G'不连通这时，由已知条件可知G'恰好含有两个分支G:和G2且V(G,)川≥5(i=1,2)。如果G,中含有Y中点，则V(G:)1≥n-1。下面分两种情况进行讨论 ①G1和G2同时含有Y中点。这时1V(G,)≥n-1(=1,2)。如果G:和G2同时含行X中点，则G:(i=1,2)至多含有 X中3个点，且G:和G2不能同时含有X中3个点。现在再分两种情况来讨论。 (a)设V(G:)l=n-1,则1V(G2)|=n+1 这时Y中任何一点∈V(G:),都与V(G:)中所有点（在G,中）相邻。对于X中任一点 x∈V(G1),如果V(G:)中有一点y使得￥yEE(G),那么d。(x)≥2n+1-3-(n+1)= H-3,否则有d。(x)≥m-4,从而6(G,)≥n-4>V(G1+3,同理可证(G≥n-3> 2 严(G:)1+3,因此G,(任=1,2)为Hamilton连通。这时不难证明H:中有至少4条边莲结G: 2 484

献〔〕。关于圈的研究已有很多结果，但关于边不交的圈的研究却不算多。刘振宏〔 “ ’ 证明了偶数阶一型图有两个边不交的圈。本文作者 ‘ ’ 证明了偶数阶一型图有边不交的两个。立圈和一个一因子。最近本文作者之一亡 ” ’ 证明了阶一一型图有两个边不交的圈除类图外。〔，证明了偶数阶。一型图有边不交的一个。圈和一个一因子。本文将证明阶一型图口 ‘ 李有边不交的两个圈和一个一因子。引理为了证明本文的主要定理，先介绍一些引理。引理〔 “ 〕设是具有占的简单图，，‘ ，任口且。。〔 ‘ 。令口。。，，二犷一。一，二 “ ， “ 任。， “ 。，，。如果乙，李。。，，或者囚乙。，。， “ 且、，则是图当且仅当是乞图。引理匕 ” 设是具有镇且尺口、的简单图，，。任。 ‘ 且。〔。如果。一伙一，那么是图当且仅当口。是。图。图在引理和下的闭包仍用表示。引理设‘ 是。阶一型图，令二 “ ‘ ， ‘ 〔犷，则成一引理证明是比较简单的，略证。引理设是阶一型图且占，则口具有边不交的一个。圈和一个一因子使得‘ 一一证明显然中含有边不交的一个 “ 。 “ 圈和一个一因子。令 ‘ 二一一，，一，二一，二 ‘ 任口，幻《玛，犷一。由引理可知成。一。如果 ‘ 是一连通，则引理成立。因此设 ‘ 不是一连通。下面分两种情形来证明。产不连通这时，由已知条件可知 ‘ 恰好含有两个分支，和，且川 ‘ 二，。如果 ‘ 中含有中点，则 ‘ 一。下面分两种情况进行讨论 ① 诊和 ‘ 同时含有中点。这时犷、一了二，。如果和同时含有中点，则口 ‘ 二，至多含有中个点，且 ‘ 和不能同时含有中个点。现在再分两种情况来讨论。设犷一，则厂口卜，这时中任何一点任厂，都与，中所有点在，中相邻。对于中任一点二〔厂，如果中有一点使得二夕任口，那么 ‘ ，幻十一一二，，二厂 ‘ ，一，否则有。，川。一从而 ‘口一 ” 、诀匕一十。同理可证叔 ‘ 一李 ” 曰乃切 ’ 廿、 ” 一，，、 ’ ‘ “ 一、一土产一 ’ 一 ‘ 一 ’ “ 。 ’叫 ’ 切跳一、一乙产一 ‘ ’ 。夕州，因此， “ ，为。连通。这时不难证明中有至少、条边连结

和G2,从而容易证明在H2中可选取适当的Hamilton圈C使k(H。-C)≥2即k(G-C-N) ≥2，故引理成立。 (b)设1V(G:)1=n,则1V(G2)l=n 对于任一点v∈V(G1),显然V(G2)巾有一点u使得uvEE(G),从而dc,()≥2n+1-3 -(n+2》=n-4,因此有6(G≥P(G,)1+1+2,同理有6(G)严(G)1+1+2。故 2 2 G:(=1,2)是Hamilton连通。由于|Y|n+1且dc,(w)n-2(i=1,2)(v∈Y),故不难证明在H2中有至少4条边连结G,和G2,这时容易可证在H2中可选取适当的Hamilton圈 C使得K(G-C-N)22。故引理成立。 ②G'中只有一个分支含有Y中点（不妨设是G2) 由引理3，可知V(G2)川>n+1且G〔V(G:)门为完金图。显然G2中不含有X中任何点且6(G)≥V(G:)引-4。不难证明6(G2)≥2n+1-3-(V(G:)儿+2)≥V(G2)引-4≥ V(Gl+3,故G,为Hamilton连通。如果V(G,!≤6，则不难证明引理成立，因此设 2 V(G)引≥7，下面分两种情况来讨论。 (a)设V(G1)川=7。如果在H2中H有至少4条边连结G,和G2,则不难证明可选取适当的Hamilton圈C使得《(H2-C)≥2，否则，在H,中N至少有8条边连结G,和G2,这时可选取适当的1-因子N' 使得k(H1-N')≥2，于是引理成立。 (b)设V(G1)引8。如果N中（在H1中)有至少3条边连结G1和G2,则同上一样可证引理成立，故设在 H,中N有至多2条边连结G,和G2,由此可以推出H中（在H2中）至少有4条边连结G1和 G2(否则，就有u∈V(G1)和v∈V(Gz),使得uw∈E(G)且d。(u)≤IV(G,)川，dc(v)≤ V(G2)川，从而有d(u)+d(v)≤2n,矛盾)。这时不难证明引理成立。 (2)G′是连通但非2-连通。此时将割点或割边删除，这时与情形(1)一样可证引理成立。引理5设G是2n(n≥13)阶Ore-(1)型简单图，H和W分别是G中的Hamilton圈和1-因子且H和N是边不交的。如果a(G-H-N)≥9，那么k(G-H-N)≥2 从引理4的证明过程中可知此引理成立。 2主要定理定理：设G是2n(n≥13)阶Orc-(1)型图且d(G)≥7，则G具有边不交的两个Hamilton圈和一个1-因子。证明：由引理4可知G中有边不交的Hamilton圈C和1-因子N使得k(G-C-N)≥2：设 G。=G-C-N,X={x:x∈V(G)且d(x)≤n),Y=V(G)-X。由引理3可知IX|≤n-1, 且Y[≥n+1,现在分两种情形来证明。情形1a(Go)≤6(G,) 这时考虑在引理1和2下所定义的闭包G。 485

和口，从而容易证明在中可选取适当的圈使双一，故引理成立。设厂二，则二对于任一点 ” 任工，显然 ‘ 。中有一点 “ 使得 “ ” 任，从而心即此夕一一。一一二，卜，因此有咨，，同理有‘ ‘ 卜 ’夕鱼一巨工十。故 “ 二，是连通。由于 ” 一且。 ‘ ” 〕、，，一， “ 任，故不难证明在中有至少条边连结，和，这时容易可证在。中可选取适当的圈使得以一一。故引理成立。 ② ’ 中只有一个分支含有中点不妨设是由引理，可知厂。且〔犷〕为完全图。显然中不含有中任何点且占召，异一。不难证明一一厂一犷，二、二二二、一，一，，二、，。、。，、」 ” 。叮气巡十 “ ，故为 “ “ ，。 ” 连通。如果、，镇“ ，则不难证明引理成立，因此设犷、，下面分两种情况来讨论。设犷，二。如果在中有至少条边连结，和，则不难证明可选取适当的圈使得、〔一，否则，在中至少有条边连结和召，这时可选取适当的一因子 ’ 使得以，一 ‘ ，于是引理成立。设厂。如果中在中有至少条边连结和，则同上一样可证引理成立，故设在中有至多条边连结和，由此可以推出中在中至少有条边连结和否则，就有任 ‘ 和任厂 “ ，使得。。毛甲右且。。簇，。簇犷，从而有镇，矛盾。这时不难证明引理成立。产是连通但非一连通。此时将割点或割边删除，这时与情形一样可证引理成立。引理设是 ” 阶一型简单图，和分别是中的圈和一因子且和是边不交的。如果一一，那么袱一一从引理的证明过程中可知此引理成立。主要定理定理设是阶。一型图且口，则具有边不交的两个圈和一个一因子。证明由引理可知中有边不交的圈和一因子使得《一一。设 ‘ 。二一一，二引名任且叼镇，，二厂一。由引理可知毛。一，且酬。十，现在分两种情形来证明。情形。。这时考虑在引理和下所定义的闭包

(1)6(G)≥7 对于Y中任意两点u和v,若uuEE(G),则0c。(“,)≤2n-(dc。(u)+dc。(U)≤4，故对任一点xERc,(u,v),有dc。(x)≥6≥0c。(,v)+2,从而x∈R:。(u,0),放R。(“,) =R。,(u,),于是由引理1可知uw∈E(Go),从而G,(Y门为完全图。再由引理3可知 d。(x)≥n(x∈Y)。对任意一点x,∈X,设Z。={y1y￥。EGE(G)}。由于d(￥o)+d(y)≥ 2n+1(y∈Zo),故do。(￥g)+dc。(y)≥2n-5,从而0c,(xg,y)=2n-dc,(xo)-dc。(y)≤ 5,从而dc,(v)≥7≥6c,(x,y)+2(对任意∈Rc。(x,y),于是∈R台。(x,y),从而 Ro。(xo,y)=Rc。(x,y)。由引理1可知xy∈E(G)。而1Z。l=2n-1-d(x)≥n-1 且2二Y,故da。(x)≥n-1。再由引理2可知对于任一点4∈Y,有x,u∈E(Gg),于是G, 是完全图，故G。有Hamilton圈。从而定理成立。 (2)6(G。)≤6 设dc(w)=d(G),则dc(w)≤9且IRc(w)川≥2n-10≥n+3。由于Rc()中任一点u有 de(u)≥2n-8,故da,(u)≥2n-11,从而GCRc(w)门为完全图。对任意y∈Y,u∈Rc(w),若 vyEE(Ga),则d后。(v)≥2n-11且da。(y)≥n-2,从而de。(o)+da,(y)≥2n,故uy∈ E(G。)于是GCY)为完全图。下面分4种情形来讨论。 ①IX1≥9 在这情形下，G,cX)为Hamiltoni连通，由k(Ga)≥2可知G。为Hamilton图，故G。有 Hamilton圈，于是定理成立。 ②1X1=8,则IYT=2n-8 令Z1=《xdc(x)≥10}，与情形(1)一样可证G〔Z,)为完全图 (1) (a)X中至少有两点u,和u2使得d。(u)≥10(i=1,2)。这时、对任一点y∈Y,0c。(u1,y)≤2，而6(G0)≥4，故R6(u1,y)=Rc。(“,y), 由引理1可知u,y∈E(G。),因此dn(u,)≥n+6(i=1,2),这时G,〔YU{u1,42}门为完全图，从而Y中任意一点y,da(y)≥2n-7 (2) 不难证明X-{u1,u2}中至少有一点u3使得d(u3)≥8 (3) 否则：设d(x,)=7(x。∈X-{u1,u2}).令2=ylyx,年E(G)},则d。(y)≥2n-6(y∈ Z),而Zl=2n-8,故ec(X,Y)≤2(n-7),而ec(Y,X)≥3(2n-8),矛盾，因此(3)式成立。由引理1及(2)、(3)可知u3y∈E(Gg)(对于任一y∈Y).因此，G,〔YU{“1,42,“}〕为完全图，这时da,(y)≥2n-6（y∈Y),再由引理1可知G,为完全图，故G。有Hamilton圈。 (b)X中至多有一点u。使得c(u,)≥10 这时d(G)≥8（否则若6(G)=7,设d(w)=7,那么|R。(w)川=2n-8,dc(y)≥2n-6 (y∈Rc(w).由于|Y1=2n-8,故ec(Y,X)≥3(2n-8),ec(Y,X)≤n-7+12+1=n+6,矛盾)，从而d(G。)≥5.由k(G,)≥2，可知Y中至少有两点y:和yz使得do(y:)≥2n-8(i= 1,2).由引理1可证明y,在G。中与所有点都相邻，因此(G。)≥6，再由引理1可知G。为完全图，故定理成立。 ③5≤X!≤？这情形类似于(b)可证定理成立。 ④1X≤4则1Y1≥2n-4.由6(G,)≥4及引理2可知G。为完全图。故定理成立。 486

。对于中任意两点“ 和，若 “ ，百，则。。 ‘ ，镇一。。 “ 。。 ” ，故对任一点“ 任。。， “ ，有。。。 “ ， “ ，从而‘ 任丢。 “ ，” ，故丢。， “ 二凡。， “ ，于是由引理可知。。〔瓦，从而万。〔〕为完全图。再由引理可知心。幻 ” “ 任。对任意一点二。任，设。二沙气任。由于二。夕任。，故。。 ‘ 。。一，从而。。 “ 。，二 ” 一 ‘ 。。一。。，从而。。 “ 。。。，对任意任。。。，，于是“ 任丢。。，，从而。。 ‘ 。，二。。。，，。由引理可知〔。。而二 “ “ 一少。二且。二，故心。 ‘ 。 ” 一再由引理可知对于任一点“ 〔，有 “ 任。，于是。是完全图，故。有圈。从而定理成立。。落设 ‘ 。二，则 ‘ 。且。二一 ” 。由于。〔二中任一点有。》卜，故。一，从而。〔。〕为完全图。对任意任， ” 任。 “ ，若，百。，则〔，一且妻。一，从而叮。。。。，故任。于是。〔〕为完全图。下面分种情形来讨论。 ① 川在这情形下，。〔〕为连通，由‘ 。可知。为图，故。有圈，于是定理成立。 ② ，则二 ” 一令谧。，与情形一样可证。〔〕为完全图中至少有两点 “ 和。使得 ‘ 。 ‘ ‘ ，。这时 · 对任一点夕〔，。。。，，夕，而 ‘ 。，故吕。 “ ‘ ，。。 “ ‘ ，，由引理可知“ ‘ ‘ 。，因此。 “ ‘ ，，这时 ‘ 。〔口 “ ，， “ 〕为完全图，从而中任意一点’ 。妻 “ 一不难证明一。，中至少有一点使得。否则设。。〔一，，。。令孟二伽夕。去，则。一少任孟，而孟一，故。，成一，而。，一，矛盾，因此式成立。由引理及、可知夕任。对于任一夕任。因此，。〔，。，。〕为完全图，这时。一任，再由引理可知。为完全图，故。有 “ 。 “ 圈。中至多有一点 “ 。使得苗。。。这时否则若，设二，那么。。一， ‘ 夕妻。一夕〔。。由于一，故，一，。，一二，矛盾，从而。由以。，可知中至少有两点和使得心。，一 ‘ 二，。由引理可证明 ‘ 在。中与所有点都相邻，因此叔。，再由引理可知。为完全图，故定理成立。 ③ 这情形类似于可证定理成立。 ④ 镇则州。一由叔。及引理可知。为完全图。故定理成立

惰形2a(G,)≥0(G。)+1 在这种情形下，分两种情况来讨论。 (1)6(G)≤n-4 设dc(w)=6(G),由于对于任意一点v∈R。(w)有dc(u)≥n+5。且dG,(v)≥n+2, 故G〔RG(w)门为完全图。因为|R:(w)川≥n+3,故任意一点v∈Rc(w),da,(v)≥n+2, 而da,(y)≥n-2(y∈Y),故"y∈E(G。)(这里的G。表示Bondy定义下的闭包)，这时 GCY)为完全图，又G〔X)为完全图，因此，(G,)≤4≤(G).这时和情形1一样可证G。有Hamilton圈，故G,有Hamilton圈。 (2)6(G)≥n-3,则6(G。)≥n-5≥8 在这种情形下，考虑G的扩充闭包G。首先给出扩充闭包G。的定义：“设G。是简单图，如果G,中有Hamiltor加圈，则定义G,的扩充闭包G:为K1to1,如果G,没有Hamilton圈，则定义G,的扩充闭包为G:且G。满足：(a)V(G:)川=1V(G。)川且E(G。)三E(G).(b)G: 不是Hamilton图，但对于任何uu年E(G),G;+uv是Hamilton图。如果“(G。)≤d(G。),这时用情形1一样的方法，不难证明定理成立。因此设a(G。)≥ 0(G。)+1,从而a(G。)≥n-4≥9 (4) 令h=a(G。)。如果G,有Hamilton圈，则已证明，故设G,中没有Hamilton圈。设T={u1, 42,,“}是G中的最大独立点集；令S=V(G)-T.不妨设d:(u1)=max{dc:(u)u∈ T},d6:(u)=max{dc:(u)引u∈T-{u:},由h≥n-4≥9，而T中最多有3个度数在G中小于n+1的点，因此dc:(“)≥n-2且cg(“)≥n-2。由扩充闭包的定义可知，在G:中有一条Hamiltom Po:(“1,“:)连结u1和u,假设在P6:(u1,4)上点的顺序排列T和S中的点为S=}01,v2,…,v2m-},T={u1,“2,…,“},不雅得到2n-h≥h-1,故h≤n。现在证明n≥h≥n-1且G8中有长为2n-1的圈。 (5) 事实上，设A={v,v:∈S,v141∈E(G)》,故|Al≥dcg(“1)-1≥n-3且We: (u)nA≥(dcg(“)+|A|)-INc:()UA|≥n-2+n-3-(2n-)=h-5≥4.由于 Nc:(u)∩A中不存在点U,使得0："1二P。(“1,“),故必有u,∈T,v,∈N6:(u,)∩A使得dc:(4,)≥#-2且v,“0+2=Pc:(“1,“),因此在G:中有一长为2n-1的圈H=Pc:(u1, v,)U{wu}UP-:(u,v+1)U{知1u},故Nc:(u,)=V(H),这时a(G)≥dc:(u)+ 1≥n-1,故(5)被证。对于任意u∈T和v∈S,设uv在E(G。),由扩充闭包的定义可知在G。中有一条连结u和 v的Hamilton路Pc:(“,v),不妨设在Ps:(“,0)上从u到v排列T和S中的点为T={u=4,u, …,u》.S={wi,v,",2-s=}。显然若uv∈E(G)(u;∈T),则u在Pc。(u,v)上的下一个点不能和u相连结 (6) 令D(u)={o:∈Slu使E(Ga)},则lD(u)l=2n-h-dc:(u)。由(6)可知ec:(v, T)≤lD(u)l,不妨设dc:(ui)=min{dcg(w)lu∈T,dct(u)≥n-2},lNc:(o-s)nTl= max{lN:(o)nTl:v∈D(ui)}。记D=D(ui),B-〈u∈TlNo:(u)nD≠}，则ID|≤3 且ec:(v,T)≤3(v∈D) (7) (现在证明当|Di=3时，|B1=5:当|D1≤2时，1B|≤3 (8) 事实上，如果D|≤2，则ec:(v,T)≤|D≤2(v∈D),由(6)和(7)可知1B|≤3。如果|D|=3且ec8(D,T)≤7，这时有h=n-1,从而不难证明1B≤5。现在设D|=3且 487

情形。。在这种情形下，分两种情况来讨论。一设。功二，由于对于任意一点 “ 任。功有 ” · 且 ‘ 。， ” ，故。〔。 ‘ 〕为完全图。因为。却，故任意一点〔。 ‘ ，。，而。。一，故。夕任瓦这里的瓦表示定义下的闭包，这时 ‘ 。〔〕为完全图，又〔〕为完全图，因此，万。镇叔瓦这时和情形一样可证。有圈，故。有圈。占李称一，则。一在这种情形下，考虑。的扩充闭包言。首先给出扩充闭包‘ 言的定义 “ 设。是简单图，如果。中有圈，则定义。的扩充闭包为。。，如果。没有圈，则定义。的扩充闭包为言且言满足厂言犷。且。言不是图，但对于任何庆言，言。是图。如果 ‘ 言毛忿，这时用情形一样的方法，不难证明定理成立。因此设李言，从而口言》一》令言。如果。有圈，则已证明，故设。中没有圈。设二左， “ ， … ，。是 ‘ 言中的最大独立点集令二一 · 不妨设。言 “ 一 “ 。言 “ “ 〔科，心解 “ 。桃 “ 任一恤，由 ” 一列，而中最多有个度数在 ‘ 中小于 ” 的点，因此 ‘ 七 “ ， ” 一且心。 ” 一由扩充闭包的定义可知，在言中有一条 “ ‘ 言， “ 。连结，和，假设在。，、上点的顺序排列和中的点为。，。， … ，。。一、，，，， … ，。。，不难得到一》一，故。现在证明》一且忿中有长为一的圈。事实上，设 ” ‘ “ ‘ 任， “ ‘ ，任忿，故。言 “ 一一且万。言。门咭 “ 。一心。一一一一一由于 ‘ 言 “ 、中不存在点” ‘ 使得“ ‘ “ ‘ · 、心，， “ 。，故必有，任， “ ‘ 任忿。使得 ‘ 言 “ ，》一且， ‘ ， ‘ · 二 ‘ 忿“ ，，，，因此在言中有一长为一的圈，， ‘ 日 “ ‘ “ ，一子岔 “ ， ‘ ， ‘ · ，故。言，犷，这时言 ‘ 言 “ ，一，故被证。对于任意。任和任，设。去 ‘ 言，由扩充闭包的定义可知在言中有一条连结。和。的 “ 路。言 “ ， ” · 不妨设在尸 ‘ 言 “ ， “ 上从 “ 到 “ 排列和中的点为丈 “ 二 “ ， “ 二， … ， “ 扑扣笠， “ 熟 “ · ， “ 氛一、二 “ 卜显然若衅 ” 任加任，则可在尸咭， ” 上的下一个点不能和 “ 相连结令谧， ‘ 任 ‘ 偌言，则一一。七由可知。七 “ ，，不妨设。忿“ 。言 “ 任， ‘ 言 ” 一， ‘ 言二。一。自 ‘ 忿 “ 自任笠。记盆， “ 任 ‘ 咭 “ 自笋价，则且咭，，，任现在证明当二时，当】镇时，簇事实上，如果蕊，则。忿，蕊簇任，由和可知。如果且‘ 舒刀，簇，这时有 “ 一，从而不难证明簇。现在设二且

ec:(D,T)≥8，显然ec(D,T)≤9。设D={v-A,,v}。设1N(u)1T1=3,u 是在Pc(ui,:-s)上的顶点，u∈Nct(o)nNc:(U2-),放P=Pct(ui,v)= Pc:(ui,)U{uu?-s}UP-:(v2-s,v:)是一条Hamilton路连结u{和：。由(6)可知 Nc:()nNn()≠中，同理如果|Nc:()nTI=3那么Nc:(w)nNn(v)=中，放B= (Nc:(o)nT)二UN(o),从而(8)得证。 ED v∈D 现在证明对于任何u∈T,v∈S-D,有uv∈E(G:) (9) 事实上，如果存在u和u(u∈T,v∈S-D)使得uv∈E(G)则|TnRc(w)川≥h-min (D(u,)lu,ETnR(v)h-(2n-h-max(do(u)luTR(u)))max(d(u,) |4:∈TnR6(u)}-2≥n-4≥9，因此，|(T-B)nRG:()1≥4，这时存在点u∈(T-B) nR。t(o)使得dc:(u)≥n-2,但dc:(u)≤S-D|+1≤dc:(u1)-1,矛盾，放(9)得证。下面根据(7)来分3种情形讨论。 ①ec:(.-A,T)=|D|=3则h=n-1,且1S1=n+1。设D={o2:-A,v:,v},则在Gg中有一条Hamilton路Pc:(u1,v2:-)由(6)和(9)可知在B中存在两点u'和u"使得u'v2-A,u“v2m-&∈E(G8)且u'i,u";EPc:(i,U2:), 故dcg(u')≥|S-D1+2≥n且dcg(u")≥|S-D1+2≥n,从而u'u"∈E(G8),矛盾。 ②ec:(v2m-,T)=2 显然{D川卡1. (a)Di=3,设D={w4,;,v2.-},则h=n-1,由于在G8中有一条Hamilton路 Pc:(ui,-s),则ec:({,T)≥2或者ec:(,T)≥2。如果|B=2,则不难证明 dcg(u')≥n且dc:(u)≥n(u',"∈B),于是u'u“∈E(G),因此设|B趴≥3，这时B中有 3个点u',u",u'"使得u'u2:-,u",u'吲∈E(G).又因Nc:()n(S-D)车中且Nc: (v)∩(S-D)+中，由(9)可知，G8有Hamilton圈，矛盾。 (b)|D1=2.设D={-,},则h=n且IB引≤3，因此ec:(u,T)=2。 (b1)1B|=3。设B={u,u”,u"},4'5-,u"-,u"',u"1∈E(G)。又因 d6:(u)≥n(u∈S-D),于是GCS-D]为完全图。因此dc:()≥2n-3(u∈S-D).由 d(G)≥4可知uv.-A∈E(G)且u:∈E(G)(对于任何v∈S-D),故d。；（v.-A)≥n 且dc:(U)≥n,从而？-∈E(G8),于是dc:(2。-h)≥n+1且i.-ku'"∈E(G)(因 dc:(u")≥n-1),所以ec:(ui-A,T)≥3，矛盾。 (b:）B|=2,设B={u',u"},不难证明dc:(u')n且dc:(u")≥n,于是u'u∈E (G),矛盾。 ③ecg(.-,T)=1,则1B≤D1≤3且h>r-1 如果D=3,设D={o?.-,v,v},由扩充闭包的定义可得在G。中有一条Hamilton 路Pc:(ui,-),于是D中有一点（不妨设为u)使得uu1三Pc;(u1,.-)且 4;,+1∈T,因此{Nc:()∩T1≥2，矛盾。如果|D1=2,设D={w2:-,},则h=n, 同上一样可证得ec:(1,T)≥2，矛盾。因此|D1=1且1B川=1，设D={v,:-}和B=u}。由(9)可知dc:(o)≥n(w∈S-D),于是GS-D]为完全图。因此dc:(w)≥2n-2(u∈S- D)。故uv.-a∈E(G8)且vu'∈E(G),因此d:(v,:)≥n,dc。(u')≥"，GCS门为完全图。这时在G。中，对于(T-B)中任一点都不与V2:-s相邻，而(T-B)中任意一点4有 488

。言，，显然是在 ‘ 忿 “ 空，二。一、 ‘ 忿，。设 “ 笠一，犷，李。设吧 ‘ 门一， “ 上的顶嘛，任代丁门万魂蛋一，故 ‘ ，，仁〕，，日二一、日一丢忿一，，勺是一条路连结 “ 丁和莎咋万。忿杏口， “ 忍笋价，同理如果。七口丁门。扩从，“ ’ 门 ’裂黔 ‘ “ ’ ，从而 ‘ ，得证。那么咭李口，戈二由可知二功，故二、现在证明对于任何 “ 任，任一，有。任七事实上，如果存在 “ 和 “ 任， “ 赶一使得 “ “ 任加则朴飞咋 “ 妻一王 “ ‘ “ ，任门 ‘ 七一一一。七川 ‘ 妞自。艺弋 ‘ 咭 ‘ 卜 ‘ 任门。忿一夕一，因此，又一口。七妻，这时存在点任一口。忿使得。忿一，但。舍一。七一，矛盾，故得证。下面根据来分种情形讨论。 ① “ ‘ 言盆一、，则一，引。设一， “ 犷，了，则在言中有一条路。言 “ ，卜 “ 二一 ‘ 由和可知在中存在两点 “ ’ 和 “ “ 使得 “ ’ “ 一。， “ 护口一、任豁且 “ ’ “ ， “ ’ “ 李任尸。言， “ 一，故。言 ‘ 一》 ” 且。七 “ 护》一 ” ，从而“ ‘ 护任兮，矛盾 ② “ ‘ 言 “ 蛋一，显然午。口卜，设。李，。，麦。一 ‘ ，则一，由于在言中有一条路咋生，蛋一，，则 “ 。言 ‘ ，或者 ‘ “ 二，。如果，则不难证明 ‘ 忿 ‘ ” 个点 ‘ ， “ 尸且。言 “ ” ‘ ， “ “ ，， “ 使得。产二一。， “ 。犷任，于是 “ ‘ “ 扩任韵，因此设，这时中有， “ ’ ‘ “ 沃以 · 又因咭叮自一刀牛价且咭自一今价，由可知，言有圈，矛盾。，设谧“ 茎一。，， ‘ ，则且镇，因此。言” ‘ ，。二。设弋产，扩，。扩声， ’ 。盆。一。， “ 。二二一，。 “ 尹。乍， “ 弋任。 ‘ 言 “ ” “ 任一，于是肛一〕为完全图。因此宫“ 一 “ 任一心可知 “ “ 乳一，任吉且“ “ 犷任言对于任何 “ 任一，故 ‘ 言 “ 蛋。一、又因由》且 ‘ 言丁乡 ” ，从而 ” ‘ “ 乳一、任 ‘ 加，于是心言 “ 氛一 ” 十且 “ 扒一、 “ ’ “ 任加因心忿 “ ’ 护一，所以。。一，，矛盾。卜，设二 ‘ ， “ “ ，不难证明 ‘ 言 “ ‘ 且 ‘ 忿 “ 异，于是 ‘ “ 任吉， ③ 矛盾。 ‘ 言二一。，，则毛且夕一如果路尸。言 “ 仁，设此。一。，叫，川，由扩充闭包的定义可得在 ‘ 言中有一条 “ 二二一、，于是刀中有一点不妨设为 “ 二使得 “ 丁 ” 犷“ 了，尸。言卜 “ 茎一且犷，，任，因此七 “ ‘ 自，矛盾。如果，设二 “ ‘ 一， ‘ ，则，，川同上一样可证得已 ‘ 言 “ ‘ ，，矛盾。因此且卜，设一和 “ ，。由可知人言 “ ” “ 任一刀，于是言〔一〕为完全图。因此心言 “ 一 “ 〔。故 “ ” 二。一任幻且 “ “ ‘ 任加，因此叭忿 “ 一，异 ” ，心言 ‘ ” ，言〔〕为完全图。这时在忿中，对于一中任一点都不与一相邻，而一中任意一点 “ 有，

dcg(u)≥#-1。设B′={u∈T1dc(u)≤n-3},则1BI≤3。注意到若uu度E(G:),则 uv庄E(G)。设B。=BUB',令 f=1E(C)nE(H2〔T-B'门)，g=|E(C)nE(H2〔S-D])I (a)B。=B,则h=n 不难得到e(,TD≥1（对于uET-B,因此f≥T-B-ee,T-B,BUD)】≥ 2 ”-)4≥4，故在E(C)nE(H,CT-B)中有两条独立边，于是在T-B中存在两点 2 和u"使得(a1),'u"∈E(C),且(a2)如果有一点v∈S-D使得ec,(w,TB)=1,那么Nc。 (v)n{u',u"}=Φ 另外，g=lE(C)nE(H2LS]|-ec(D,S)=IE(C)nE(H2CT))川-ec(D,S)≥ ”,1-2≥4，设C=…u'w…uu…u5u3…u5ug…v4…是H,中的Hamiltoa圈。注 2 意其中{和ivi,vui,gvg,vgu4}=E(C)nE(H,〔S-D])。因为ec。(u',S-D)≥ea (u°，S-D)≥|S-D|-1≥n-2,因此有t∈{1,2,3,4}使得u'v4,u"v:∈E(G。）。用0'表示 ;,用v"表示u?。因此在Hz中有一条Hamilton圈C′=C-{u'u",v'v"}U{u'v",u"v"},令 G0=H2-C'。于是有a(G)≥m-1≥12。由引理5可知，k(G)≥2，这时不难证得C(G6) n-1。如果v2-u'年E(Go),则a(G)=n,显然a(G。)≤a(G)=。若c(G,)=# 一1，那么|D引≠1，这时不难证明定理成立。若a(G。)=n,则同上一样，可选取另一个 Hamilton圈C”≠C'使得a(H2-C")=n-1。因此可设v2:-u'∈E(G,),这时a(Gg) =n-1,a(G。◆)≤G(G)=n-1,从而不难证明D≠1，故G6°=K2,于是定理成立。 (b)B。≠B 知柴B,l=,那么1≥T-B,-e(TB,B,UD》≥”0≥放f≥2， 2 9≥f+ec(T-B,B。)-ec(S-D,D)≥3。如果2≤|B,≤3，则不难证明f+9≥4且 f>1,9≥1。于是在T-B。中有两点u和u”,在S-D中有两点'和v"使得u"u,'v” EE(C)。设H=…u'u"…v'v"…,且u'v',u"v"∈E(G。),这时类似于(a)的证明可得到定理成立。因此定理证毕。本文心1988年元成的参考文献 1 Bondy J A and Murty U S.Graph Theory with Applications,Macmillan, 1976 2 Win S.,A Sufficient Condition for A Graph to Contain Three Disjoint 1-Factors,J.Graph Theory,1982:6 3刘振宏。数学学报，1987：5 4李明楚，李忠祥。北京科技大学学报，1991,13(2)：186一190 5 Li Mingchu.Two Edge-Disjoint Hamilton Cycles,Preprint,1989 6朱永津，李浩。曲阜师大学报，1985：2 489

咭一。设 ’ 〔少。。 “ 毛，，一，则 ‘ 蕊。注意到若 “ “ 班，。曦言。设。口 ‘ ，令自〔一 ‘ 〕，自〔一〕。二，则二，，不难得到。。。，习对于任一，因沙爪已工二旦匕生互胜丛旦里卫冲，一 ’ 一一一，，，一、一，， ” 、，一、，、，一。，。，一 ‘ 一一一万－乡，改在右七少乙一〔月一刀，甲有阴余朔立迈，士足侄一万甲仔仕网点解自和 “ 使得， ‘ “ 任，且如果有一点，八 “ ，， “ 必另外，夕门〔〕一。， “ 任一使得。。 “ ，一，那么 “ 。二】门〔〕卜。，乒忿一一，设 “ · ‘ ’尸一叮叫毗畔一叫畔 “ · 毗弓一是中的圈。注意其中 ‘ 笠，蛋 ” ， “ 兰兰，二复二自〔一〕。因为。。 ‘ ，一李。口，一一一一，因此有任，，，使得 ‘ 。叮，丁任。。用。 ‘ 表示川，用 “ 表示川。因此在中有一条圈，一扭 ‘ 。 “ ，。 ‘ “ 扭 ‘ ” “ ，。 “ ” “ ，令石万一 ’ 。于是有石一。由引理可知，、石，这时不难证得石乡一。如果二一。，敏。，则石。，显然石簇石二。若石 ‘ “ 一，那么刀劳，这时不难证明定理成立。若石，二，则同上一样，可选取另一个圈护并 ‘ 使得一 “ 二一。因此可设。万一。 ‘ 任。，这时 “ 幻。一，吼 ’ 簇吼一，从而不难证明】护，故石一 · ，于是定理成立。。笋二。、。、，，。，一。一 “ 。一。，。期术气幻那各多－－一万一一－－沪号卫、音故 ‘ ，夕夕。一。，。一。一刀，刀》。如果簇。，则不难证明夕》且妻，。于是在一。中有两点 “ ‘ 和 “ “ ，在一刀中有两点。 ‘ 和 “ 使得 “ ， ‘ ， “ ‘ “ 任。设二 … 。 ‘ “ “ 一，俨 … ，且 “ ‘ ‘ ，。 “ 。 “ 任。，这时类似于的证明可得到定理成立。因此定理证毕。本文怂工年完成的参考文献主，，一，一，，刘振宏。数学学报，李明楚，李忠祥。北京科技大学学报，，一。一，，朱永津，李浩曲阜师大学报