D0I:10.13374/j.issm1001-053x.1991.02.016 北京科技大学学报 第13卷第2期 Vol.13 No.2 1991年3月 Journal of University of Science and Technology Beijing March 1991 关于Ore-3型图-Win猜想的部分结果 李明楚*李忠祥* 摘要:证明了Win猜想对:=3成立。实际上,且得到了更好的结论:2n(n>10)阶 Orc-3型图中存在边不交的两个Hxmi1ton圈和一个1-因子,且对8(G)=5而言,结论是 最好可能的。 关键词:Hamilton图,Orc-3型图,因子 On the Graphs of Ore-Type-(3)-A Result of Win's Conjecture Li Mingchu'Li Zhongxiang' ABSTRACT:It is proved that Win's conjecture is true for k=3.A better conclusion is obtained.There exist two Hamilton cycles and a 1-factor which are edge-disjoint in a Ore-type-(3)graph of order 2n (n>10).Moreover,this result is best possible for 6(G)=5. KEY WORDS:Hamilton cycle,Ore-type-(3)graph,factor 本文所讨论的图均为无向的简单图。设G是一个简单图,用G表示G的闭包,用6(G) 和a(G)分别表示G的最小度和独立数,用G〔R)表示点集R在G中的导出子图,用Pc(u1, “k)=“1u2…u:表示G中以41和4:为端点的一条路,设A,B2V(G),Rc(A)=V(G) -〔AU(UNc(@)门,ec(A:B)=I{uv∈E(G)lu∈A,v∈Bl.其余没有说明的符号见文 EA 献E1). 给定非负整数k,若图中每一对不相邻顶点u和v,都有d(u)+d(w)≥IV(G)|+k,则 称G为Ore-k型图。Ore-k型图有许多性质,比如Ore-k型图是k-Path-Hamilton图等 1990-09-11收稿 ·数力系(Department of Mathematics and Mechanics) 186
第 卷第 期 年 月 北 京 科 技 大 学 学 报 。 关于 一 型图一 猜想的部分结果 李明楚 ‘ 李忠祥 ‘ 摘 要 证明 了 猜想对 二 成立 。 实际上 , 且得 到 了更好 的 结 论 。 。 。 阶 一 型 图中存在边 不交 的两个 圈和一 个卜因子 , 且对 占 句 而言 , 结论 是 最好可 能的 。 关健词 圈 , 一 型 图 , 因 子 一 一 一 ‘ ‘ 夕 “ ’ 夕劣 夕 。 , 吞 一 一 一 一 五 , · , 一 一 , 本文所讨论的图均为无向的简单图 。 设 是一个简单图 , 用 表示 的闭包 , 用 和 分别表示 的最小度和独立数 , 用 〔 〕表示点集 在 中的导 出子图 , 用 ‘ 。 ,, 。 。 … 表示 中以 和 为端点的一条 路多 设 , 只 犷 , 。 厂 一 〔 ‘ 〕 , 。 。 〔 任 , ‘ 任 其余没有说明的符号见文 任 献〔 夕 。 给定非负整数 , 若 图 中每一对不相邻顶点。 和 , 都有 十 川 乡 存, 则 称 为 一 型 图 一 型 图有 许多性质 , 比 如 一 舟型 图是 卜 一 图 等 一 一 收稿 数 力系 皿 DOI :10.13374/j .issn1001-053x.1991.02.016
等。对于具有偶然点的0re-k型图,1982年Win.S给出了下列猜想: 若G是2阶Ore-k型图,则G具有边不交的k+2个1-因子,其中0≤k≤2n一4。 1987年刘振宏【2)证明了对k=2Win猜想成立。本文证明了Win猜想对=3成立。 以下分别简称Hamilton圈和Hamiltoni连通为H-圈和H-连通。 1引 理 为了证明本文的定理,首先介绍一些引理。 引理1【3】设a(G)≤k(G),则简单图G有H-圈。 引理2【4】设G是n阶连通度为(G)(k(G)≥1)的简单图且a(G)≤6(G),则对Ha- milton性质而言,闭包运算的稳定度为n-(K(G)-1)。 引理3r5)设G是Ore-k型图,k≥0,IV(G)I≥3,则G是k-Path-Hamilton图. 引理4e】设G是n(m≥20)阶Ore-0型图,且6(G)≥5,则G具有两个边不交的Ha- milton圈, 引理5设G是2n阶0re一3型图,令Z={2∈V(G),d(z)≥n+2},则|Z1≥n+1. 引理6设G是2n阶0re-3型图且6(G)≥7,x。∈V(G),d(x)≤n,Z。={z|zE V(G),x。2EE(G)},如果G中还存在一点y。∈V(G)使得d(y。)≥d(x)+1且与Z。中至少 一点不相邻,则G具有边不交的两个H-圈和一个1一因子。 证:设22∈Z。且之2y。EE(G)。因d(x)≤n故 |Z。|=2n-d(x。)-1≥n-1,从而对任意一点2∈Z。有:d(2)≥(2n+?-d(x。)≥n+3,于是 在G〔Z]中有dccz。)(2)≥n+3-d(x)≥3,故在G〔Z,]中存在长为3的路p=(z1z223z4), 由引理4可知在G中存在H~圈C。Pp(这里C,与p均表示边之集合)。令G1=G-C。,这时 不难证明G,中有H-圈,取G1中的一个1-因子N。令G。=G1~N。现在证明G。中有H-圈。 事实上,考虑闭包Go。由da。(z)≥n(2∈2,)可知G。〔Z〕为完全图,从而d后,(z:)-1 (i=2,3)且d,(2,)≥d(z,)-2(i=1,4)。由已知条件有a.(y)≥d(x)-2,又由 d(xg)+d(22)≥2n+3可知dā,(y)+d后。(z2)≥2n,从而y,22∈E(Go),而yz2∈E(G), 故da。(22)≥d(22)且da,(y)≥d(×)-1,从而da,(22)+dan(x,)≥2n,于是x。22∈ E(G),从而推出了da。(x)>d(x)-2且da。(zz)≥d(z2)+1,因此d后(xg)+d后。(z)> d(x)-2+d(23)-1≥2n,故×oz3∈E(Go),推出了d元。(xo)≥d(xo)-1且da。(z3)≥d(23)。 了 同理可证xo2;∈E(G,)(j=1,4)且d元。(xo)≥d(xo)+1,da。(2;)d≥(2,)-1(j= 1,4)。由此可知xo2∈E(G0)(对任意2∈Z),于是得到了d元。(xo)≥d(x0)-3+2n- d(x)-1≥2n-4,由6(G。)≥4可知在G。中x。与所有点都相邻,从而G。〔Z。U{x}门为完 全图且|Z。U{xo}I≥n,于是 da。(2)≥d(2,)(=2,3) (1) 不难证明对于任意z∈Z。有2yo∈E(G),这时G〔Z。U{xoya}门为完全图且 dao(yo)≥n (2) 现在证明2:(i=2,3)在G。中与所有点都相邻 (3) 187
等 对于具有偶然点的 一 吞型 图 , 年 给 出了下列 猜想 若 是 阶 一 型图 , 则口具 有边不交 的 十 个 一 因子 , 其 中 毛 一 。 年刘振 宏 〔 “ 〕 证明 了对 猜想 成立 。 本文 证明 了 猜想对 成立 。 以下分 别简称 圈和 连通为 一 圈和 一 连通 。 引 理 为 了证 明本文的定理 , 首先介绍 一些 引理 。 引理 〔 “ ’ 设 毛 ‘ , 则 简单 图 ‘ 有 一 圈 。 引理 〔 ‘ ’ 设 是 阶连通 度为秃 庵 ‘ 的 简单 图且 簇 , 则 对 性 质而 言 , 闭包运算的稳定 度为。 一 一 。 引理 ‘ ” ’ 设口是 一 掩型 图 , , 厂 , 则 是 一 一 图 引理 〔 “ ’ 设 是 。 阶 一 。 型 图 , 且 , 则 具 有两 个边不交的 。 圈 。 引理 设 是 阶 一 型 图 , 令 ‘ 任 犷 , , 则 多 。 引理 设 是 阶 一 型 图且 , 。 任 犷 , 。 毛 , 。 二 二 」二 任 犷 , 二 。 吞 , 如果 中还存在一点 。 任犷 使 得 。 异 二 。 且与 。 中至少 一点 不 相邻 , 则 具有边不交 的两 个 一 圈和一个 一因子 。 证 设 二 任 。 且 翔 。 乙 。 因 。 故 。 卜 一 。 一 。 一 , 从而对任意 一点 任 。 有 的 一 。 。 十 , 于 是 在 〔 。 〕 中有 ‘ 〔 。 〕 ‘ 一 “ 。 , 故在 〔 。 〕 中存在长 为 的 路 , 由引理 可知在 中存在 一 圈 。 这 里 。 与 均表示边 之集合 。 令 , “ 一 。 , 这时 不 难证明 , 中有 一 圈 。 取口 、 中的一个卜 因子 。 令 。 一 。 现 在 证明 。 中有 一 圈 。 事实上 , 考虑闭包刁 。 。 由 。 。 任 。 可知 讯 〔 。 〕 为完全图 , 从而 气 ‘ 一 ‘ , 且 。 “ , , 一 , 由已知条件有 万。 。 。 一 , 又 由 。 “ 可知 。 。 歹。 ‘ , , 从而 。 “ 任 。 , 而 。 “ “ 乙 , 故 。 “ ‘ 且 。 夕 。 。 一 , 从 而 。 “ 。 , 。 , 于 是 ‘ 。 ‘ 任 。 , 从而推出 。 。 。 一 且 。 “ , 因此 。 。 。 ‘ ‘ 。 一 ‘ 一 , 故‘ “ 任 “ ,推出 。 ‘ 妻 一 且 。 ‘ , “ 。 同理可证 。 , ,〔 。 , 且 。 。 。 妻 。 , 。 “ , “ , 一 二 , 。 由此可知 。 二 任 。 对 任意 二 任 。 , 于是得到 。 一 二 。 一 一 , 由 。 可知在 。 中二 。 与所有点都相邻 , 从而 。 〔 。 二 。 〕 为完 全图且 。 二 。 , 于是 ‘ 之 ‘ , 不 难证明对于 任意 任 。 有二 。 〔 。 , 这 时 。 〔 。 二 。 , 。 〕为完全 图且 。 。 。 现在 证明 ‘ , 在 。 中与 所有点都相邻
事实上,若x2,E(G)(i=2,3),则d(x)+d(z:)≥2n+3,由(1)可知dan(x)+da。(2) ≥2n,故x2:EE(G。),从而d,(2)≥2n-4(i=2,3)。由6(Go)≥4可知(3)成立。 这时G。为3-连通。由(2)可知d。(2)≥n+1(2∈Zo),而任意一点u∈Z-Z。(2={z2∈ V(G),d(2)≥n+2})有da。(u)≥n-1,故uz∈E(Go)(2∈Z),由Z,U{xo}1≥n和(2)可知 石〔ZU{x}门为完全图,于是a(G,)≤d(G),由于对任意u2,EE(G)有d。(2)+d。 ()≥2n-1(j=1,4),从而uz,∈E(G。),故z,(j=1,4)在G,中与所有点都相邻,于是(G) ≥5。这时有α(G,)≤42n-5 +2n-5≥2n,故u,“;∈E(Go),从而G〔B1为完全图。又因da。(x:)+d元,(u;)≥2m-5+2n -8≥2n+1,故x:u,∈E(G),从而da。(x:)≥2n-6,于是x,xx∈E(G0)(牛k),(i=1,2, ,5;j=1,2,…,2n-6),故GCB1UB2〕为完全图,从而G是完全图,故G,有H-圈。 (2)3≤n≤6当n=3时,G为完全图,显然命题成立。当n=4,5,6时,G分别含有 如图所示的生成子图(见图1),从图中可知命题成立。且结论是最好可能的。 命题2。设6(G)=6且n≥9,则G具有边不交的两个H-圈和一个1-因子. 证:设d(xo)=6(G),Z。={2|2∈V(G),xo2EE(G)},则|Z,|=2n-7且对任意点 2∈Z。有d(2)≥2n-3。这时G具有边不交的两个H-圈和一个1-因子,否则,则选取一个边 数最多且满足已知条件的反例G,使得对任何uEE(G),G+4v具有边不交的两个H-圈 和一个1-因子。这时还可以证明: 对任何u,v∈E(G),uvEE(G),则d(u)+d(v)2n+5 (5) 188
事实上 , 若 “ ‘ 乙 , , 则 “ , 由 可知 。 。 “ ‘ , 故二 二 ‘ 任 。 , 从而 。 二 ‘ 一 ‘ , 。 由‘ 。 可知 成立 。 这时 。 为 一 连通 。 由 可知 。 “ “ “ 任 。 , 而 任意 一点 “ 任 一 。 仕 任 厂 , “ ” 有 。 一 , 故 “ 任 。 “ 任 。 , 由 ‘ 。 乡 和 可知 仇 〔 以 , 。 〕为完 全图 , 于是 。 落 。 , 由于对任 意 “ “ , 吞 有 。 “ , 。 “ 一 , , 从而 “ 之 , 任 。 , 故 “ , , 在 。 中与所有点都相邻 , 于是耘 。 。 这时 有 云 。 镇 壳必 。 。 由引理 可知瓦有 一 圈 , 故 。 有 一 圈 , 因此 引理得 到 了证明 。 引理 设 是简单 图 , “ , 乙 且 十 时 犷 ‘ 一 , 则 有 一 因 子 且仅 当 口 四 有 一 因子 。 关于 猜想 的 部分结 果 在 以 下 证明 中均 设口是 阶 一 型 图 。 设 川 任 , 镇 , 川 任 , 夕 , 二 任 , 二 , 二 任 犷 , 二 , 二 二 二 〔 厂 , 二 , 则 , 日 且 口〔 〕为完全图 。 为 了证明定理 , 首先给出 个命题 , 然后 由这 个命题 , 就证明 了定理是对的 。 定理的 内 容在本 节后 。 命 题 。 设 , 则 口具有边不交的两 个 一 圈和一个 一 因子 , 且这 个结论 是 最好 可能的 。 证 设 劣 。 二 , 则 中有 一 个点与 二 。 在 中不 相邻 , 设为 , 。 , , 幻 ” · , 。 一 , 由 二 。 ‘ 妻 作 可知 , ‘ 一 , , 一 , , 一 , 从而 。 。 一 。 设 。 , 二 , … , 二 , 则 ‘ 一 , 且 ‘ 与 中每 点都相邻 。 显然 ‘ 中有边不交 的 一个 一 圈 。 与一个 一 因子 令 。 二 一 。 一 万 , 这时 有 。 “ 。 , 。 劣 ‘ ” 一 £ , , , , 且 。 ‘ 一 , , … 一 。 ” 由于 中任意两 点 ‘和 , 今 , 在 。 中有 。 “ ‘ 。 , 一 一 乡 , 故 , 任 。 , 从而 。 〔 〕为完全图 。 又 因 。 ‘ 。 , “ 一 一 , 故 ‘ , 任 。 ,从而 。 ‘ 一 , 于 是“ ‘ 、 任 今 , , , ” · , , , ” · , 一 , 故 。 〔 日 〕为完全图 , 从而 。 是完全 图 , 故 。 有 一 圈 。 毛 当 二 时 , 为完全图 , 显 然命题成立 。 当 。 二 , , 时 , 分 别含有 如图所示 的生成子 图 见 图 , 从图 中可知命题成立 。 且结论是最好 可能 的 。 命题 设 ‘ 且 。 , 则‘ 具有边不交 的两个 一 圈和一个卜 因子 证 设 。 , 。 二 任 犷 , 二 。 〔 , 则 】 。 一 且对任意 点 任 。 有 幻 一 这时 召具有边不交的两个 一 圈和 一个 一 因子 , 否则 , 则选取一个边 数最多且满足 已知 条件的 反例 口 , 使得对任何训 吞 , 十 “ 具有边不交的两个 一 圈 和一个 一 因子 。 这时还可以 证 明 对任何 “ , 。 任 , 。 乙 , 则 。 。 成
0 2,我=4 b.n-5 c. =6 图1G的生成子图的示意图 Fig.1 The spaning subgraph of G 由(6)可知G〔Z,)为完全图。 对于任何一点u∈V(G),若d(u)≥9,则u在G中与Z。中所有点都相邻 (6) 设与x。相邻点的集合为B,设B′={y∈B|yz∈E(G),对于任何z∈Z。},则IBI≥3,否 则若1B|≥2n-3,取GC2。]中长为3的路p=(z12223 24),由引理6可知在G中存在一个H圈C。一P,令G1=G-C0,不难证明G,有H-圈.取G1 189
图 的 生 成子 图的 示 意图 王 江 由 可知 〔 。 〕 为 完全图 。 对于 任何一点 任犷 , 若 “ , 则 “ 在 中与 。 中所有点都相邻 设与 。 相 邻点的 集合为 , 设 ‘ 二 夕 任 夕 任 , 对于 任何 任 。 , 则 ‘ 】 , 否 则若 ‘ , 不妨 设 , , 则 尹 。 一 ’ 一 。 即 。 , 亦即 一 毛 , 矛盾 。 当 时 , 由于对任意 任 产有 。 一 。 可知 〔 勺为完全图 ,从而 〔 。 口 勺 为完全图 。 显然对 “ 任 一 矛, 有 。 “ , 否则 ,若设 。 。 二 , 由于 “ 。 至少 与 。 中一点不 相邻 , 这时类似于引理 的 证明 可以得 出矛 盾 。 因此 〔 一 〕 为完全图 。 由 。 可知存在 。 , , 任 产, 夕 。 , 夕 , 任 一 尹 。 使 得 。 。 夕。 , 。 少 任 且 。 。 今 , 夕 。 姜夕 。 分别选取 〔 。 尹 〕和 〔 一 ‘ 口 。 〕中的 一 路 〔 。 。 。 ‘ 〕 “ 。 , , 和 。 〔 刀 一 , 毛 二 。 〕 夕 。 , 夕 , ,令 。 , 口 口 。 , 夕 且口 , 二 一 。 , 不难证明口 有 一 因子 , 令 ‘ 。 二 口 一 这 时 。 〔 。 勺 为 完全 图 。 从 。 的取法 可知在 中有两 条边二 ,二 , 使得 ‘ 任 。 , , , 且 , 二 , “ 任万 , 于是有 “ ‘ “ ‘ 一 , 而 占 。 , 故 。 ” 一 “ , , , 即 妻 , 而 。 镇 , 由引理 可知 。 有 一 圈 。 于是命 题得证 。 命 题 。 设 功 , 且 , 则 具有边不交 的两 个 一 圈和 一个 一 因子 。 证 因 功 , 故截 , 取 中的 一 因子 , 令‘ , 一 万 , 则夕 是 。 一 。 丝 图 , 由引理 可知 中有边不交的两 个 一 圈 从而命题得 证 。 命题 。 设 日 姜功 , 粉 少且乙 , 则 具有边不交的两 个 一 圈和 一个 一 因子 。 证 若命题不成立 , 则 可选取 使得 是具有边数最多 的且满足 已知条件的 反 例 。 此 时 由 可知 〔 〕 为完全图 。 设 。 任 , 。 川 。 任 。 则 】 。 卜 一 。 一 一 。 显然对 任 , 夕 任 口 , 有二 任 由引理 可知对 任犷 口 , 任 。 有 任 , 于是 由 十 李 卜 。 一 。 一 其 中 任 , 可知 , 且当 任 时有 毛 且 日 今功则 〔 , 从而 一 , 取 〔 。 〕 中长 为 的路 二 勺 , 由引 理 可知在‘ 中存在一个 圈 。 , 令 一 。 不 难 证明‘ ,有 一 圈 取
中的一个1-因子N,令G。=G1-N,则G〔Z)为完全图,从而d后,(2)≥n+2(i=2,3), d后。(2》≥n+1(j=1,4).由于da。(2)≥n-1(z∈Z),故有22,∈E(G)(i=1,2, 3,4),从而da。(2)≥2n-4(j=1,2,8,4),故x2,∈E(G0),从而da。(x) ≥d(xo)-3+4=d(xo)+1.由此可知xo2∈E(G)(对于2∈Zo),因此da。(xa)≥2n-4 d后。(u)≥n+1(u∈Zo),从而对于任意u∈Z。在G,中与所有Z中点都相邻。由此可知 da(u)≥2n-4(u∈Z),而|ZgU{x}l=n,故8(G)≥",从而G。有H-圈,故G。有 H-圈. (2)Y=中这时Z,卡中。类似于上面的证明可得出矛盾于是命题得证。 命题5.设YUZ1=中,8(G)≥7且X牛,则G具有边不交的两个H-圈和一个1-因子。 证:如果|X1≤3,则很容易证明命题成立。设引X≥4,若命题不成立,则选取边数最 多且满足已知条件的反例G,此时由(6)可知G〔Z)为完全图。显然IZ1≥n+2且|X引≤n-2 (否则,如果|Z1=n+1,则由1X|≥n-1有ec(Z,X)≥3(n+1),而与ec(X,Z)≤2 (n-1),矛盾)又因K(G)≥2故ec(Z,X)≥2且有z1,z2∈Z,x1,x2∈X使得z:x:∈E(G) 且x1卡x2,21卡22(=1,2).显然在G〔Z幻和GCX)中分别存在H-路P1=P。c2,(21,22)和 P2=Pccx)(x1,x2)。令C,=P1UP2U{21x1,22x2}则C。是G中的H-圈,不难证明G-C。 中有1-因子N.令G。=G-C。-N。由|Z1≥n+2可得在N中存在一条边e=u使得“1v∈Z 且u中2,v丰z,(i=1,2)。显然G〔Z)为完全图,于是d后o(w)≥d()且da(w)≥d(w). 而对任意x∈V(G),有da。(x)≥d(x)-3。 (10) 若ux∈E(G),则由do(u)+dao(x)≥d(u)+d(x)-3≥2n可知x∈E(G).从而 d后。(4)≥2n-1。同理可证da(w)≥2m-1,故K(G)≥2,由G。〔Z)及G〔X)为完全图可 知a(G。)≤8(G)。由于对任意z∈Z-{21,22}有d后。(2)≥d(2)-1,由引理2及上面的证 明可得d:。(2)≥2n-2,而|Z-{21,z2}1≥n,故K(G)≥n.因此G。是完全图,于是命题得证。 定理:设G是2n(n≥10)阶Ore-3型图,则G具有边不交的两个H-圈和一个1-因子, 且对6(G)=5而言结论是最好可能的。 证:由命题1至命题5可知定理成立。 参考文献 1 Bondy J.A.and Murty U S R.Graph Theory with Applications,The macmi- llan press,Londen,1976 2刘振宏。关于Win猜想的部分结果,数学学报,1987:5 3 Win S.,A Sufficient Condition for A Graph to Contain Three Disjoint 1- Factors,J.Graph Theory,1982:6 4朱永津,李洁。图论中的Hamilton问题,曲阜师范大学学报,1985,(2) 5 Kronk H V.A Note on K-Path-Hamilton Graphs,J.Comb.Theory, 1969,7:977 6 Li Hao and Zhu Yongjin,Edge-Disjoint Homilton Cycles in Graphs, 科学院系统所,PH.D Thesis,1988 190
中的一个 一 因子 ,令 。 , 一 , 则 。 〔 。 〕 为完全图 , 从而 。 ‘ , ’ , , 。 ’ , · 由于 。 一 “ 任 , 故有“ ‘ , 〔 。 , , , , 从而 。 “ , 一 , , , , 故 ,任 , 从 而 。 。 。 一 。 · 由此 可知 任 对于‘ 〔 。 , 因此 。 , 。 一 。 ” 十 〔 。 , 从 而 对 于 任 意 “ 任 。 在 。 中与所有 中点都相邻 由此 可 知 。 一 “ 任 。 , 而 。 , 故 占 。 , 从而 。 有 一 圈 , 故 。 有 一 圈 巾这时 ,等毋 。 类似于上面的 证明可得 出矛盾于是命题得证 。 命题 设 巾 , 己 了且 簧万 , 则‘ 具有边不交的两个 一 圈和一个 一 因子 。 证 如果 尤 , 则很容易证明命题成立 。 设 , 若命题不成立 , 则选取边数最 多且满足 已知条件的反例 , 此时 由 可知 〔 〕为完全图 显然 且 一 否 则 , 如 果 。 , 则 由 一 有 ‘ , 李 , 而 与 ‘ , 。 一 , 矛盾 又 因 尤 ‘ 故 。 。 , 李 且有 二 , 二 任 , , , 〔 使得 二 ,二 ‘ 〔 ‘ 且二 姜二 , 今 二 , 。 显然在 〔 〕和 〔 〕 中分别存在 一 路 。 〔 〕 二 ,, 二 和 。 〔 〕 , 。 令 。 , 则 。 是 中的 一 圈 , 不难证明 一 。 中有 一 因子 令 。 一 。 一 。 由 可得在 中存在一条边 二 “ “ 使得 “ 任 且 。 今二 ‘ , 。 今 ‘ ‘ , 。 显然 万 。 〔 〕 为完全图 , 于是 。 “ 。 且 。 。 。 而对任意二 任 犷 , 有 若。 二 一 。 若 〔 , 则 由 子。 。 万。 一 可 知 “ 二 任 。 从而 若。 一 。 同理可证 若。 一 , 故 , 由 。 〔 〕及 〔 〕 为完全图可 知 。 瓦 叔 凤 。 由于对任意 任 一 二 , 好有 。 习 幻 一 , 由引理 及上面的 证 明 可得 于。 习 一 , 而 一 二 , 幻 , 故 ‘ 。 。 因此 。 是完全图 , 于是 命题得证 。 定 理 设 是 叮 阶 一 型 图 , 则 具有边不交的两个 一 圈和一个 一 因子 , 且对 占 而言结论是最好可能的 。 证 由命题 至命题 可知定理成立 。 参 考 文 献 · 五 , , , 刘振 宏 。 关于 猜想 的部分结果 , 数学学报 , 。 , 五 , 。 , 朱永津 , 李洁 图论中的 向题 , 曲阜师范大学学报 , , 一 一 , 。 , , , 一 , 中国 科学 院系统所 , , 马