关于Ore-(1)型图中的Hamilton圈

D0I:10.13374/j.issn1001-053x.1992.04.031 第1卷第4期 北京科技大学学报 Vol.14 No.4 1992年7月 Journal of University of Science and Technology Beijing Ju1y1992 关于0re-(1)型图中的Hamilton圈 李明楚李忠祥 摘要：1982年Win证明了：2n阶Orc-(i)型图G有边不交的一个Hami1ton圈和一个 1-因子。本文证明了：在几乎与Win定理的条件相同的情况下，Or-(1)型图有边不交的两 个Hami1ton圈和一个1-因子。 关键词：Hamilton圈，l-因子，0re-(1)型阳 Hamilton Cycles in the Graphs of Ore-Type-(1) Li Mingchu'Li Zhongxiang' ABSTRACT:It was proved by S.Win in 1982 that if the sum of the degree of nonadjacent vertices of a simple graph G of order 2n is at least 2n+1,then G has a Hamilton cycle and a 1-factor which are edge-disjoint.In this paper,it is proved that,under almost the same condition as Win's theorem,has at least two Hamilton cycles and a 1-factor which are edge-disjoint, KEY WORDS:Hamilton cycle,1-factor,Ore-type-(1) 本文所讨论的图均为无向简单图。用6(G)和a(G)分别表示图G中的最小度和点独立数， 用△(G)表示G的最大度。设A二V(G),B二P(G),令R.(A)=V(G)-〔AU(UN。(a)门， eG(A,B)={uv:u∈A,v∈B,uD∈E(G)‖。设Pc(u1,4)=41424,表示G中从41到u4 的一条路，令P。'(u,“1)=““:-1“1。一个图G称为Ore-(k)型图，如果对任何一对不 相邻顶点u和v都有d(u)+d(v)≥V(G)‖+k(k为整数)。其它没有说明的术语和记号参见文 1991-08-29收稿 敦学力学系(Department of Mathematics and Mechanics) 483

第 卷第 期 北 京 科 技 大 学 学 报 。 。 年 月 刀 。 。 关于 一 型图 中的 圈 李 明楚 李忠祥 摘 要 年 证 明 了 ，阶 一 型 图‘ 有边不交的一个 圈和 一 个 一 因子 。 本文证明 了 在几乎与 定理 的条件相同的情况 下 ， 一 型 图有边不交的 两 个 圈和一个 一 因子 。 关健词 。 圈 ， 一 因子 ， 。 一 型 图 一 一 “ 犷 口口 。 召 ， 一 一 。 ， ， ， 一 一 ， 一 ， 一 一 本文所讨论 的图均为无 向简单图 。 用叔 和 分别表示图 中的最小度和 点独立数 ， 用△ 表示 的最大度 。 设 二犷〔 ， 二 犷 ， 令 。 。 ， 丈。 。 任 ， 任 ，。 任 。 设 ‘ ，。 。 一 〔 。 〕 ， 。 〔 。 …“ 表示 中从。 到 。 的一条路 ， 令尸万’ 。 。 ， 。 ， 二 ，价一 二 ， 。 一个图 称为 一 型 图 ， 如果 对 任 何 一对不 相邻顶点 。 和， 都有 ， 犷 为整数 。 其它 没 有说明 的术语和记号参 见文 一 一 收稿 · 数学 力学系 五 瓜 几 通 城 萦 DOI ：10．13374／j ．issn1001－053x．1992．04．031

献〔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

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