图中有边不交的3个1─因子的一个新充分条件

D0I:10.13374/i.issn1001053x.1994.03.019 第16卷第3期 北京科技大学学报 Vol.16 No.3 19946 Journal of University of Science and Technology Beijing June 1994 图中有边不交的3个1一因子的一个新充分条件 李明楚)王兵团) 熊黎明2) 1)北京科技大学数力系，北京100083 2)江西师范大学数学系 摘要Win于1982年证明了2n阶Oe-(1)型图有边不交的3个1-因子，本文改进这个结果，得 到一个新的充分条件：2n(m≥10)阶2-连通Oe-(-2)型图G有边不交的1个Hamilton图和1 个1一因子，除非G是附图中所示的图之一. 关键词Ore-(-2)型图，I-因子，Hamilton圈 中图分类号0157.5 A New Sufficient Condition for A Graph to Contain Three Disjoint 1-Factors Li Mingchu)Wang Bintuan Xiong Liming?) 1)Department of Mathematics and Mechanics.USTB,Beijing 100083.PRC 2)Jiang xi Normal University ABSTRACT It was proved by S Win in 1982 that every Ore-type-(1)graph of order 2n has a Hamilton cycle and a l-factor which are edge-disjoint.In this paper,we obtain the-following theorem:Every 2-connected Ore-type-(-2)graph G of order 2n(n>10)has a Hamilton cycle and a 1-factor which are edge-disjoint unless G is one of the graphs in Figure. KEY WORDS Ore-type-(-2)graph,1-factor.Hamilton cycle 本文所讨论的图均为无向简单图.一个n阶图称为O爬-(k)型图，如果对任何一对不相 邻点u和v都有d(u+d(@≥n+k(k为整数).用δ(G)△(G)和x(G)分别表示图G的最小 度、最大度和独立点数.设A,BcVG),令R(A)=V(G)-[AU(N)川，ec(A,B)=|uw ∈E(G):u∈A,v∈B}l设Pc4,4)=44uk是G中从山1到4的一条路，则令P。(uk,u) =4“-4,其它没有说明的术语和记号参见文献[1小， 关于图中边不交的Hamilton圈和1-因子的研究是一个比较困难的问题，且目前研究 得不多.李明楚和李忠样4.]证明了Ore-(3)型图有边不交的两个Hamilton圈和一个1-因 子，刘振宏l31证明了Ore-(2)型图中有边不交的Hamilton圈.Win.SI2】证明了Oe-(l)型 图中有边不交的一个Hamilton圈和一个1-因子.Schmeichel和Hayes[)证明了2n阶(n≥6) 1993-01-05收稿 第一作者男30岁副散授理学颈士

第 卷 第 期 年 月 北 京 科 技 大 学 学 报 龙 图中有边不交 的 个 一 因子的一个新充分条件 李 明楚 ’ 王 兵 团 ‘ 熊黎 明 北 京科 技 大学 数力 系 ， 北京 刃 江 西 师范大 学 数学 系 摘要 于 年证 明 了 阶 一 型 图有边不 交 的 个 一 因子 本文改进这个结 果 ， 得 到 一 个新 的充分条件 ” 阶 一 连通 一 一 型 图 有边 不 交 的 个 图 和 个 一 因 子 ， 除非 是 附 图 中所示 的 图之 一 关键词 一 一 型 图 ， 一 因 子 ， 圈 中图分类号 亡 一 巧 ’ 体公 夕 块 即 以 “ ，“ ， ， 夕 川 一 叮 一 一 。 而 一 一 ， 一 一 一 一 一 一 万 一 一 一 ， 一 ， 本文所讨论 的 图均 为无 向简单 图 一 个 阶 图称 为 一 型 图 ， 如果 对任何 一 对不相 邻 点 和 都 有 为 整 数 用 占 和 分 别 表 示 图 的 最 小 度 、 最大度 和独立 点数 · 设 ， ， 令 · ，一 ‘ ，一 ‘ 日 ‘ ，，， ， “ · ， ，一 ，。 令 “ 任 ， 刃 任 设 凡 ， 、 … 、 是 中从 ，到 、 的一条路 ， 则令 云 ‘ 、 ， 二 “ … ， 其它没 有说 明的术语和记号参见 文献 关于 图 中边 不 交 的 圈和 一 因子 的研 究 是 一 个 比较 困难 的 问题 ， 且 目前 研 究 得 不多 李 明楚 和李忠祥 ’ 〕证 明 了 一 型 图有边 不 交 的两个 圈 和 一 个 一 因 子 刘 振 宏 ’ 证 明 了 一 型 图中有边 不 交 的 圈 ’ 证 明 了 一 型 图 中有边 不交 的一个 圈和 一个 一 因子 珍 和 〕 证 明了 阶 卯 一 一 收 稿 第一 作者 男 岁 副教授 理 学硕 士 DOI ：10．13374／j ．issn1001－053x．1994．03．019

.290. 北京科技大学学报 1994年No.3 2-连通Oe-(-2)型图G有一个Hamilton图除非G是图1中所示的图(a)与(b)之一·本 文将改进上述两个结果，得到了一个有边不交的3个1-因子的新充分条件，即2阶1≥10) 2-连通且(G)≥4的Oe-(-2)型图G有边不交的一个Hamilton圈和一个1-因子除非G 是附图中所示的图之一. 1引理 为了证明本文的主要定理，先引进一些引理， 引理1171.设G是2n阶2-连通Ore-(-2)型图(n≥6).则G有一个Hamilton圈除非 G是附图的(a)和(b)中所示的图之一. 引理2161.设G是n阶具有ax(G)≤δ(G)的简单图，u.v是G中不相邻的一对顶点，令8。(u,D) =n一d(u)-d(o).R。(u,t)={x5R(u,):d(x)≥6e(u,v)+2}.如果IR。(4,川≥6e(u,),且 k(G)≥2.则G是Hamilton图当且仅当G+uv是Hamilton图. 引理31，设G是n阶具有x(G)≤(G)且k(G)≥1的简单图，u和v是G中不相邻的一 对顶点，如果d(u)+d(o)≥n(k(G)-l,那么G是Hamilton图当且仅当G+是Hamilton图. 图G在引理2和3下的闭色用G表示. 引理4.设G是2n阶2-连通Ore-(-2)型图，令X={xtV(G):d(x)≤n-2)则1X)≤ n-1且G[X灯为完全图， 引理4，的证明较简单，在此略证， 引理5.设G是2n(n≥10)阶2-连通Ore-(-2)型图且6(G)≥4.如果G不是图1中所示 的图之一，则G有一个1-因子N使得G-N为2-连通. 证明：由引理1可知G中有一个1-因子N.令G=G-N.X={xV(G):d(x)≤n-3, Y=V(G)-X.由引理4可知X≤n-1且G[灯为完全图.如果G'是2-连通，则引理已 证.因此设G不是2-连通.下面分两种情形来证明， 情形1·G'不连通. 显然，G'只有两个分支G和G,且|V(G,)川≥4(=1,2).如果G,中含有Y中的点，则V(G)川 ≥n-1.如果G,和G,中含有X中点，则G,和G,只能含有1个X中的点，否则G连通.下 面再分两种情况来证明· 1)G,和G2同时含有Y中点.则1V(G,)1≥n-1,(i=1,2) (a)IV(G)1=n-1,则1V(G)川=n+1. 这时△(G,)≤n-2而且△(G)≤n.对于X中任何一点“，如果u∈V(G),则在G:中必有一 点t使得uw年E(G),于是d(0)+d(w)≥2n-2,从而dG(m≥2n-2-1-(n+1)=n-4,因 此δ(G)≥n-4≥|V(G)/2+1.同理可证如果u∈V(G,则d。(u)≥n-3,从而δ(G)≥n-3 1V(G,)川/2+1.故G,和G均为Hamilton连通.如果N中有至少3条边e,=u,v,(i=1,2,3, u,∈V(G),V,∈V(G)连结G,和G,则在G,中有一条Hamilton路Pc,(4,4)连结4，和42， 在G,中有一条Hamilton路PG,(心，马)连结和，于是C=Pc,(,儿U{4,}UPc,(,) 是G中的Hamilton圈，从而在C上可选取G中的一个】-因子N',使得e,N',于是还容 易证明G,和G,都有Hamilton圈而且e2和e连结它们，故G-N为2-连通.如果N中恰

· · 北 京 科 技 大 学 学 报 望科 年 一 连通 一 一 型 图 有 一 个 五 图除非 是 图 中所示 的 图 与 之 一 本 文 将 改 进 上 述 两 个结 果 ， 得 到 了一个有 边不交 的 个 一 因子 的新充分 条件 ， 即 阶 。 一 连 通 且 占 的 一 一 型 图 有 边 不交 的一 个 圈 和 一 个 一 因 子 除 非 是 附 图 中所示 的 图之 一 引 理 为 了证 明本 文 的主要 定理 ， 先 引进 一些 引理 引理 设 是 阶 一 连通 一 一 型 图 则 有 一 个 耐 圈 除 非 是 附 图 的 和 中所示 的 图之 一 引理 ’ “ ， 设 是 阶具有 城 簇 占 的简单 图 ， ， 。 是 中不相邻的一对顶点 ， 令 日仄 ， 。 一 。 一 ， 。 ， 。 一 、 任 。 ， 口。 ， 如果 。 ， 。 ， ， 且 峨 则 是 耐 图 当且 仅 当 。 。 是 图 引理 ’‘ ， 设 是 。 阶具 有 城 毛 侧 且 的 简 单 图 ， 。 和 是 中不 相 邻 的一 对顶 点 如果 伪 一 一 ， 那 么 是 耐 图 当且仅 当 。 。 是 图 图 在 引理 和 下 的 闭色 用 表示 引理 设 是 阶 一 连通 一 一 型 图 ， 令 资 分 簇。 一 ， 则 簇 一 且 月 为完全 图 引理 的证 明较 简单 ， 在此 略证 引理 设 是 阶 一 连通 一 一 型 图且 占 如果 不是图 中所示 的 图之 一 ， 则 有 一 个 一 因 子 使得 一 为 一 连通 证 明 由引理 可 知 中有 一 个 一 因 子 令 口 二 一 ， 、 任以 劝 簇。 一 ， 一 由引理 可 知 簇 一 且 月 为 完 全 图 如 果 ‘ 是 一 连 通 ， 则 引理 已 证 因此设 ‘ 不 是 一 连通 下 面分 两种情形 来证 明 情形 ’ 不连通 显然 ， ‘只有 两个分 支 和 ， 且 ， 如果 ， 中含有 中的点 ， 则 川 一 如果 ， 和 中含 有 中点 ， 则 和 只能含有 个 中的点 ， 否 则 ‘ 连通 下 面再分 两 种情 况来证 明 ， 和 同时含有 中点 则 ， 一 ， ， 一 ， 则 这 时 △ 一 而且 △ 毛 对于 中任何 一 点 ， 如 果 “ 任 【 ， 则 在 中必 有 一 点 使得 诺 ， 于 是 一 ， 从 而 。 一 一 一 。 一 ， 因 此 占 一 同理 可 证 如果 。 份 ， 则 。 一 ， 从 而 占 一 故 ， 和 均 为 耐 连通 如果 中有 至 少 条 边 ， ， ， ， ， ， 呀 ， 矶任 连结 ， 和 ， 则在 中有 一 条 耐 路 。 ， 连 结 和 ， 在 中有 一条 耐 路 。 ，， 连结 、 和 ， 于 是 一 。 “ ， 日 ， ，， 日 ， 叼 是 中的 圈 ， 从而 在 上 可 选取 中的一 个 一 因 子 ’ ， 使 得 砖 ’ ， 于 是 还 容 易证 明 ， 和 都有 耐 圈而且 马 和 连结 它 们 ， 故 一 丫 为 一 连 通 如 果 中恰

Vol.16 No.3 李明楚等：图中有边不交的3个1一因子的一个新充分条件 291· 好有2条边连结G,和G,(因为G为2-连通)。设这两条边为e,=uv,(4,∈V(G,),:∈V(G) =1,2,如果G,和G2的顶点数为偶数，则类似上面的证明可得到一个1~因子N使 得e,eN,于是G-N'是2-连通的.因此设G,和G,的顶点数为奇数，则对于G中任何 一点u≠4，u。都有u与V(G)中所有点在G中都相邻，否则，若存在一点山≠4,2使得与 G,中某一点不相邻，则d()≤n-3.显然在V(G)中可找到一个点≠，，使得d()≤n 且E(G),于是d()+d()≤2n-3矛盾.同量可证对任何一点v≠，，v必与(G)中 所有点在G中都相邻，因此当，44∈E(G⑤时G[V(G)】和G[V(G)]为完全图.故G就 是附图中的(e)所示的图. (b)IV(GI=n,则IV(G)川=n. 对于任意一点v∈V(G),V(G)中必有一点u使得uwE(G),从而dc(@)≥2n-2-1-d(四 ≥n-3≥V(G)I/2+2,故δ(G)≥1V(G)1/2+2,同理6(G)≥1V(G)川/2+2，因此G1和G2是 Hamilton连通.用类似于(a)的证明方法，可以证明引理成立. 2)G'只有一个分支含Y中点（不妨设为G),. 由引理4可知1V(G)川≤n-1,而且G[V(G)】为完全图.显然V(G)PX.对于G,中任意 一点u,在G,中必找到一上点v使得uv生E(G),从而d(+d()≥2n-2,于是d。,(a)≥2n-2 -1-d()≥2n-3HV(G1V(G)1-3≥1V(G)l/2+1,从而G2为Hamilton连通.因δ(G)≥3，故1V (G)川≥4.如果N中恰好有2条边e,=4,u(u,∈V(G),v,∈V(G),i=1,2)连结G与G2.显然当 442∈E(G)时，G[V(G)]为完全图，否则，若存在一点≠，∈V(G)使得d(u)≤|V(G-2, 那么在G,中必找到一点≠u,4使得E(G,而且d()+d()≤|V(G)-1+V(G)1-2 ≤2n-3矛盾.这时G就是附图中(e)所示的图.如果N中有至少3条边连结G和G,这 时不难证明G中有一个1-因子N使得G-N”为2-连通. 情形2.G'是连通的. 如果G'中有割边，则将割边去掉，就化为情形1的证明，因此设G中不含割边·设哈 是G中的割点，G。=G-,则不难证明G。恰好有两个分支G,和G2用情形1中的证明方 法，可证G,和G2都是Hamiltion连通，且δ(G,)≥V(G,)l/2+1(=1,2).因为G为2-连通，故 在N中必有一条边e=(,∈V(G)∈V(G)连结G,和G,.因G没有割边，故分别 在G,和G,都有两个邻点（设4山，∈V(G),∈V(G,),且44a,hv,,,t5∈E(G).不妨设 4≠4，≠，那么在G,中有一条Hamilton路P,=PG,(u,42)连结4，和4，在G2中有一条 Hamilton路P,-Pc,他，)连结和，于是P=PU{kvoz}UP,是G中的Hamilton路. 在P中选取一个1-因子N,我们得到G-N'是2-连通的.因此情形2被证.故引理被证. 从引理5的证明过程中可知下列引理成立， 引理6.设G是2n(n≥10)阶2-连通Oe-(-2)型图，δ(G≥4，而且G不是图1中所示 的图之一且N是G的一个1-因子，如果x(G-M≥7，则k(G-N)≥2. 2定理的证明 定理：设G是2n(n≥10)阶2-连通Oe-(-2)型图且δ(G)≥4，则G有边不交的一个 Hamilton圈和一个因子除非G是附图中所示的图之一

李 明楚等 图中有边不交 的 个 一 因子 的一个新充分条件 好有 条边连结 ， 和 因为 为 一 连通 。 设这两条边 为 ， ‘ ， 任 ， ‘ 份 ， ， ， 如 果 ， 和 的顶 点 数 为偶 数 ， 则类 似 上 面 的 证 明 可 得 到 一 个 一 因 子 丫 使 得 ， 醉 ， 于 是 一 ‘ 是 一 连通 的 因此设 ， 和 的顶 点数为奇 数 ， 则 对于 中任 何 一点 护 ， “ ， 都有 与 中所有点在 中都相邻 ， 否 则 ， 若存在 一点 。 笋 ， 使得 与 ， 中某 一 点不相邻 ， 则 簇。 一 显 然 在 中可 找到 一 个 点 笋 ， 姚 ， 使得 毛。 且 ’ 句 ， 于是 叼 一 矛 盾 同量 可 证 对 任 何 一 点 。 笋 ， 姚 ， 。 必 与 乡中 所有点在 中都相邻 ， 因此 当 姚 ， 任 句 时 【袱 』和 【 刃 为完 全 图 故 就 是 附 图 中的 所示 的 图 卜 ， 则 对于 任意一点 份 ， 办中必 有 一 点 使得 砖 ， 从而 ‘ 一 一 一 一 ， 故 占 ， 同理 ， 因 此 ， 和 是 而 连通 用类 似于 的证 明方法 ， 可 以 证 明引理 成立 ‘ 只 有 一个分 支含 中点 不妨设 为 由引理 可 知 簇 一 ， 而且 〕 为完全 图 显然 。 对于 中任意 一点 ， 在 ， 中必 找到 一上 点 使得 举 ， 从而 一 ， 于 是 一 一 一 一 一 卜 ， 从而 为 而 连通 因 ， 故 如 果 中恰 好有 条 边 ， ‘叭 任 ， ， ， 任 办 ， ， 连 结 与炕 显 然 当 任￡ 时 ， 为完全 图 ， 否 则 ， 若存在 一 点 笋 ， 姚 任 使得 。 簇 办一 ， 那 么在 ， 中必 找 到一 点 。 护 ， 使得 砖 ， 而且 。 叼簇 一 户一 一 矛盾 这 时 就是 附 图 中 所示 的 图 如 果 中有 至 少 条 边 连 结 ， 和 ， 这 时不难证 明 中有 一 个 一 因子 ’ 使得 一 ， 为 一 连通 情形 ‘ 是连通 的 如果 ’ 中有 割边 ， 则将割边 去掉 ， 就化 为情 形 的证 明 因此设 ’ 中不 含 割 边 设 此 是 ’ 中的割点 ， 。 ’ 一 ， 则不难证 明 恰好有 两个分支 和 用情 形 中 的证 明方 法 ， 可 证 ， 和 都是 连通 ， 且占 ‘ ， 因为 为 一 连 通 ， 故 在 中必有 一 条边 。 。 。 任 ， 任 刃 连结 ，和 乓 因 ’ 没有割边 ， 故 分别 在 和 都有两个邻点 设 ， 任 ， ， 姚任 ， 且 ， 。 ， 。 ， 姚 任 · 不妨设 。 笋 ， 笋 ， 那 么 在 中有 一 条 路 ， ， ， 连 结 ， 和 ， 在 中有 一 条 口 路 凡一 凡 ， 办连 结 ， 和 姚 ， 于 是 一 口 日 是 中 的 路 · 在 尸 中选取 一个 一 因子 从 我 们 得 到 一 ， 是 一连 通 的 因此 情 形 被 证 故 引理 被证 从 引理 的证 明过程 中可 知下列 引理成立 引理 设 是 。 。 阶 一 连通 一 一 型 图 ， 占 叨 〕 ， 而且 不是 图 中所 示 的 图之一且 是 的一个 一 因子 如果 城 一 叼 妻 ， 则 一 定理 的证 明 定 理 设 是 阶 一 连 通 一 卜 型 图且 占 妻 ， 则 有 边 不 交 的 一 个 而 圈和 一个 因子 除非 是 附 图中所示 的 图之一

…292· 北京科技大学学报 1994年No.3 (b) c) ● G 1 (e) (d) 附图定理中的5个例外的0e-(-2)型图 (a)de,)=n-1或n,(i=1,2,,在+1) (b)d)=n-1或nd(v)=n-1,或n (c)d,)=n-1或n,d()=n-1或n,d()=n-l,n或n+1 (d)d)=n-1或n(i=1,2,3,4) (e)当4∈E(G),∈E(G)时G[VG)】和G[V(G)] 均为完全图.V(G)和V(G)川均为奇数， Figure The five exceptional Ore-type-(-2)graphs in main theorem 证：设G不是图1中所示的图之一，则由引理5可知G中有一个1-因子N使得G-N 为2-连通.设G。=G-N,X={x∈V(G:d(x)≤n-2},Y=V(G-X.由引理4可得|X≤n- 1而且G[)为完全图.现在分两种情形来证明， 情形1.d(G)≤6(Go 这时考虑在引理2和3所定义下的闭包G。· (1)δ(G)≥6 对于Y中任意两点u和B,若uvE(G),则0c,(u,v)≤2n-(da(侧+dc.()≤2n-(2n-(2n -2-2)=4,从而对任意一点x∈R.u,),有d)≥6≥0g。(u,)+2,故x∈R(u,), 因此R,(,)=R,u,以，于是由引理2可知uw∈E(G),故G,[Yy为完全图.再由引理4 可知对任意一点x∈Y有da,(x)≥n.对任意一点x∈X,设M,={y∈V(G):yxE(G)以 由于d(x)+d)≥2n-2y∈Mo),所以dcx)+dcy)≥2n-4,从而0c.(x,y)=2n-dc(x)- dc.y)≤4，故d6)≥6≥0c(x,)+2(U∈R(x,y)于是v∈RG(x,y),因此R(x,y)= RG.(xo,y).由引理2可知xy∈E(G).而Ml=2n-1-d(x)≥n+l,故d(x)≥n+1,因眦有 δ(G。)≥n,于是G。有Hamilton圈，故G。有Hamilton圈

北 京 科 技 大 学 学 报 燮辫 年 ， 。丫 一 “ 一 贾 气 丫丫 耐 ’ 之人尸 “ 一 ‘ 儿 十 少、 〕 一 沙。 附图 定理 中的 个例外的 一 一 型 图 。 一 或 ， ， ， · 、 比 一 或 ， 一 ， 或 ， 一 或 ， 一 一 或 ， 一 ， 或 ， 一 或 二 ， ， ， 当 姚 任 ， 叭 任 时 」和 【 」 均 为完 全 图 和 均 为奇数 匆此 一 一 一 证 设 不是 图 中所示 的 图之一 ， 则 由引理 可 知 中有 一 个 一因子 使得 一 为 一 连 通 设 。 一 ， 二 任 。 一 ， 句 一 由引理 可得 蕊。 一 而 且 【月 为完全 图 现在分两 种情形来证 明 情形 蕊占 勾 这 时考虑在 引理 和 所定义下 的 闭包 。 占 句 对于 中任 意 两 点 和 ， 若 砖 ， 则 。 ， 一 玩 。 一 一 一 一 ， 从而 对任 意 一 点 任 。 ， ， 有 。 。 。 ， ， 故 任 。 ， ， 因此 乙 。 ， 凡 。 ， ， 于是 由引理 可 知 。 。 任 民 ， 故 属 月 为完 全 图 再 由引 理 可 知 对任意 一 点 、 任 有 瓦 。 对 任 意 一 点 。 任 ， 设 分 诺 · 由于 。 。 一 ，呀 。 ， 所 以 。 。 分 一 ， 从而 。 。 ， ， 一 。 。 。 。 。 伽 簇 ， 故 小 。 ， ， 任 、 。 ， ， 于 是 任 。 。 ， ， ， 因此 。 。 ， ， 沁 ， 由引 理 可 知 ， 任 氛 而 一 一 ， 故 ， 因比有

Vol 16 No.3 李明楚等：图中有边不交的3个1一因子的一个新充分条件 293· (2)δ(G)≤5 设d(w)=6(G),则δ(o)≤6且|R(o)川≥2n-7≥n+3.因为R,(o)中任一点u有d(u)≥ 2n-8,所以da,(u)≥2n-9≥n+l,从而G[R(o)]为完全图.而对任意y∈Y,v∈R(o, 若yE(G),则dc()≥2n-8,dcy)≥n-2,于是dc,()+d,y)≥2n,故y∈E(G,从而 dcy)≥n+3,故G[门为完全图.显然|X≥4，否则，有1YI≥2n-3,于是6(G[门)≥2n-4, 而δ(G)≥3，由引理3可知G为完全图，故定理成立.显然1≤4，否则有δ(G[)≥-2 ≥(XM+1)/2,从而G[凶为Hamilton连通.由K(Go)≥2，可证G,有Hamilton圈，故G。有 Hamilton圈，从而定理成立.于是我们得到了1=4，则IY=2n-4.如果X中存在一点x。 使得d(xo)≥5，则dc,(x)≥4.又因G[Y]为完全图，故由引理3可证x与Y中点在G。中都相 邻，于是C[YU{xo}]为完全图，这时不难证明G。为完全图，故G,有Hamilton圈，从而定 理成立.所以我们得到对X中任一点x有d(x)=4,因此对X任一点x在G中恰好Y中只 有一点与x相邻.设X={,2,,},由G为2-连通可知在Y中必有两个不相同点4，” 使得（不妨设）4,4∈E(G),这时G[X☒中有Hamilton路P,=4和1-因子N'={ }而对于Y中任一点w有d(d)≥2n-2-4=2n-6≥n+4,故G[Y门有Hamilton圈.在G [门中取一个1-因子N”,则N。=N'(UN”是G中的一个1-因子.这时令G=G-N。,则 不难证明G'[门为Hamilton连通.设P,是G'[Y]中连结4，和4，的Hamilton路.令C=PU PU{4,,4}则C是G中的Hamilton圈.故定理成立.情形1被证. 情形2.x(G)≥6(G)+1 首先证明δ(G)≥n-3.否则，设d(@)=δ(G),由于对任意一点v∈R。(o)有d(u)≥n+2, 从而d。)≥n+1.故G[R(o)]为完全图.而Rc(o)川≥n+3,故6(G[R。(o])≥n+2,又 因为d,(d)≥n-2(u∈Y),故uv∈E(G),从而G,[y为完全图.而G☒为完全图，因此 x(G。)≤3≤6(G),这时与情形1一样可证明定理成立，故(G)≥n-3.这时仿照参考文献[5] 中的主要定理的证明可得到此定理成立，故定理证毕. 参考文献 1 Bondy J A,Murty U S.Graph Theory with Applications.Macmillan,New York:1976 2 Win S.A Sufficient Condition for A Graph to Contain Three Disjoint 1-Factors.J Graph Theory,1982, 6(4):489-492 3刘振宏.关于Wm猜想的部分结果，数学学报，1987,30（⑤：675~678 4李明楚，李忠祥，Or-(3)型图-Wm猜想的一个结果.北京科技大学学报，1991,13(2)：18610 5李明楚，李忠祥.关于Oe-(1)型图中的Hamilton圈.北京科技大学学报，1992,14（④：483~489. 6朱永津，李浩.图论中Hamilton问题的进展.曲卓师范学院学报，1985(2)：12-22 7 Schmeichel E,Hayes D.Some Extensions of Ore's Theorem,Graph Theory with Applications to Algorithms and Computer Science,(kalam 200,Mich;1984).New York:Wiley,1985.231~249

李 明楚等 图 中有边不交的 个 一 因子 的一个新充分条件 占 设 。 占 ， 则 占佃 簇 且 。 。 。 一 因为 叻 中任 一 点 有 一 ， 所 以 瓦 一 。 十 ， 从而 瓦 。 。 为 完 全 图 · 而 对任 意 任 ， 。 任 凡 嘛 若 即 哄 ， 则 。 一 ， 分 一 ， 于是 ‘ 。 。 。伽 ， 故 ， 任 民 ， 从 而 心分 。 十 ， 故 属 月 为完全 图 · 显然 ， 否 则 ， 有 一 ， 于 是 创民【 一 ， 而 鱿氏 ， 由引理 可 知 瓦为完全 图 ， 故定理成 立 显然 月 蕊 ， 否 则有 占 瓦 月 刹月 一 刹因 ， 从而 风 月 为 连 通 由 氏 ， 可 证 瓦有 圈 ， 故 。 有 圈 ， 从而定 理成 立 · 于是 我们得 到 了 ， 则 二 一 如果 中存在 一点 使得 ， 则 。 。 又 因 【 为完全 图 ， 故 由引理 可证 。 与 中点在 氏中都相 邻 ， 于 是 民【 日 为完全 图 ， 这 时不难证 明 为完全 图 ， 故 有 山 圈 ， 从而 定 理成立 所 以 我 们得 到 对 中任一 点 有 二 ， 因 此 对 任 一 点 ， 在 中恰 好 中只 有 一 点 与 相 邻 设 二 ， 姚 ， 叭 ， 吸 ， 由 为 一 连通可 知在 中必有 两个不相 同点 ， 姚 使得 不 妨设 ， 姚姚 任 ， 这 时 因 中有 己 路 尸 二 姚 和 一 因子 ’ 姚’， 而 对于 中任一 点 。 有 一 一 二 一 。 ， 故 〔月 有 圈 在 【月 中取一个 一 因子 ，’ 则 ’ 日 “ 是 中的一个 一 因 子 · 这 时令 ’ 二 一 ， 则 不 难 证 明 ’ 【月 为 连通 · 设 凡 是 ‘ 月 中连结 和 的 咖 ” 路 · 令 一 尸，日 凡日 ， ， 则 是 ‘ 中 的 而 圈 ， 故定理 成立 · 情形 被 证 · 情形 占 首先 证 明 占 。 一 否 则 ， 设 叻 占 ， 由于 对任意 一 点 任 。 伽 有 ， 从而 。 。 。 妻 故 民 为完全 图 而 。 伽 ， 故 占 瓦 。 。 妻 ， 又 因为 一 。 任 ， 故 “ 。 任 瓦 ， 从 而 瓦 月 为 完 全 图 而 因 为 完 全 图 ， 因 此 瓦 簇 簇 占 属 ， 这 时 与情形 一 样可证 明定理 成立 故 截 。 一 这 时仿 照 参 考 文 献 中的主要 定 理 的证 明可得 到此定理成 立 故定理证毕 参 考 文 献 助耐 ， 望 却 璐 以 止川 ， 创币 助 笼 一 幻 ， ， 叨 一 礴 刘振宏 关于 猜想 的部分结果 数学学报 ， ， 习 一 李明楚 ， 李忠祥 一 型 图 一 猜想 的一个结果 北京科技大学学报 ， 卯 ， 一 如 李 明楚 ， 李忠祥 关于 一 型 图 中的 间 圈 北京科技大学学报 ， ， 一 朱永津 ， 李浩 图论 中 间 问题 的进展 曲阜师范学 院学报 ， 一 及为几画 日 ， 娜 沈 ‘ 卫 幻 比 ， 笙幻 却 月即行山 汕 泳 ， 抽山 ， ， 一