关于Ore-3型图-Win猜想的部分结果.pdf

等。对于具有偶然点的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,)≤4<k(G。)。由引理1可知G,有H-圈，故G,有H-圈，因此引理得到了证明。引理7设G是简单图，uvEE(G)且d(w)+d(v)≥|V(G)引-1，则G有1-因子且仅当G +uv有1-因子。 2关于Win猜想的部分结果在以下证明中均设G是2n阶Ore-3型图。设X={x|x∈V(G),d(x)≤n},Y={yly∈ V(G),d(y)=n+1},Z={zz∈V(G),d(z)≥n+2},Z1={z2∈V1(G),d(2)=n+2}, Z2={zl2∈V(G),d(2)≥n+3}, 则Z=Z1UZz,V(G)=X U Y U Z且G〔XUY)为完全图。 (4) 为了证明定理，首先给出5个命题，然后由这5个命题，就证明了定理是对的。定理的内容在本节后。命题1。设6(G)=5,则G具有边不交的两个H-圈和一个1-因子，且这个结论是最好可能的。证：设d(xg)=6(G),则G中有2n-6个点与x在G中不相邻，设为B1={41,2…, u2a-6},由d(xo)+d(u:)≥2n+3可知，d(u:)≥2n-2(i=1,2,,2n-6),从而d(u:)=2n- 2。设B2=N(xo)={x1,x2,,xs},则d(x,)≥2n-5,且×，与B1中每点都相邻。显然G 中有边不交的一个H-圈C。与一个1-因子N.令G=G-C。-N,这时有d后，(x)≥2， d后。(x)≥2n-8(i=1,2,3,4,5)且da。(4:)≥2n-5(i=1,2,…2n-6)。 (1)n≥7由于B1中任意两点u:和“，（牛j),在G。中有d后。(u)+d。(u,)>2n-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|<3,不妨设1B|=2,则1B11Z。|+(|B引-|B'1(8-4)≥52|≥5×7=35即： 3|2。|≤4×4，亦即3(2n-7)≤16，矛盾。当n≥9时，由于对任意u∈B'有dc(u)≥2n-6 ≥n+8可知G〔B勹为完全图，从而G〔Z,UB门为完全图。显然对V4∈B-B',有dc(u)=6, 否则，若设d。(4o)=7,由于4，至少与Z。中一点不相邻，这时类似于引理6的证明可以得出矛盾。因此G〔B-B门为完全图由K(G)≥2.可知存在u,“1∈B',yo,y1∈(B-B)U{xo}使得40yo,“1y1∈E(G)且uo卡u1,yo卡y1分别选取G〔ZoUB门和G〔(B-B)U{x})中的H -路P1=Pot:ovn')(u0,4)和Pg=Pct(-Bu{*0}】(yo,y1),令C0=P,UP2U{uoyo, y1“}且G1=G-Co,不难证明G1有1-因子，令G。=G1-V.这时G〔ZUB)为完全图。从C0的取法可知在N中有两条边2122,2324使得2：∈Z。(i=1,2,8,4)且21,22， zs24∈N,于是有d元0(z:)≥d(z)≥2n-3,而6(G)≥3，故da。（2o)≥2n-1(i=1, 2,3,4)即K(G)≥4，而a(Go)≤4≤K(G),由引理1可知G有H-圈。于是命题得证。命题3。设X=中，6(G)≥7且n≥10，则G具有边不交的两个H-圈和一个1一因子。证：因X=p,故d(G)≥n+1,取G中的1一因子N,令G1=G-N,则G1是Ore-0望图，由引理3可知G:中有边不交的两个H-图。从而命题得证。命题4。设YUZ:牛中，X￥中且8(G)≥7，则G具有边不交的两个H-圈和一个1-因子。证：若命题不成立，则可选取G使得G是具有边数最多的且满足已知条件的反例。此时由(6)可知G〔Z]为完全图.设xo∈X,Z。={2zx,∈E(G)}.则1Z|=2n-d(xo)-1 ≥n-1. 显然对Fx∈X,y∈YUZ1,有xy∈E(G) (7) 由引理6可知对yy∈YUZ1,Z∈Z。有yz∈E(G),于是由n+2≥d(y)≥|X|+1Z。| IX|+2n-d(xo)-1(其中y∈YUZ:)可知|XI≤3，且当y∈Y时有|X|≤2且|XUy1 ≤3 (8) (1)V卡中则」XUY|≤3，从而引Z|>≥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

中的一个一因子，令。，一，则。〔。〕为完全图，从而。 ‘ ， ’ ，，。 ’ ， · 由于。一 “ 任，故有“ ‘ ，〔。，，，，从而。 “ ，一，，，，故，任，从而。。。一。 · 由此可知任对于‘ 〔。，因此。，。一。 ” 十〔。，从而对于任意 “ 任。在。中与所有中点都相邻由此可知。一 “ 任。，而。，故占。，从而。有一圈，故。有一圈巾这时，等毋。类似于上面的证明可得出矛盾于是命题得证。命题设巾，己了且簧万，则‘ 具有边不交的两个一圈和一个一因子。证如果尤，则很容易证明命题成立。设，若命题不成立，则选取边数最多且满足已知条件的反例，此时由可知〔〕为完全图显然且一否则，如果。，则由一有 ‘ ，李，而与 ‘ ，。一，矛盾又因尤 ‘ 故。。，李且有二，二任，，，〔使得二，二 ‘ 〔 ‘ 且二姜二，今二，。显然在〔〕和〔〕中分别存在一路。〔〕二，，二和。〔〕，。令。，则。是中的一圈，不难证明一。中有一因子令。一。一。由可得在中存在一条边二 “ “ 使得 “ 任且。今二 ‘ ，。今 ‘ ‘ ，。显然万。〔〕为完全图，于是。 “ 。且。。。而对任意二任犷，有若。二一。若〔，则由子。。万。一可知 “ 二任。从而若。一。同理可证若。一，故，由。〔〕及〔〕为完全图可知。瓦叔凤。由于对任意任一二，好有。习幻一，由引理及上面的证明可得于。习一，而一二，幻，故 ‘ 。。因此。是完全图，于是命题得证。定理设是叮阶一型图，则具有边不交的两个一圈和一个一因子，且对占而言结论是最好可能的。证由命题至命题可知定理成立。参考文献 · 五，，，刘振宏。关于猜想的部分结果，数学学报，。，五，。，朱永津，李洁图论中的向题，曲阜师范大学学报，，一一，。，，，一，中国科学院系统所，，马