资源描述：
《hamilton—连通图的一个充分条件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Hamilton—连通图的一个充分条件I—l第12卷第2期无锡轻工业学院JOURNALOFTHEWUXIINSTITUTEOFLIGHTINDUSTRY已,V01.121993NO.2Hamilton一连通图的一个充分条件查起兆吴正声(无锅轻工业学院)(南京师范大学)摘要证明1下列结论,设G是^一连通的H阶无环图,^≥2,若对G中任意^一独立^一l集,x一{.,】,……4—1),有三IⅣ(x—X)I>(点一1)H,则G为Hamilton一连通I0因.关键词Hamilton一连通图}^一连通图}^一独立集0引言阁也本文涉及的图都是无环的(
2、但可能有重边的)无向图.设_G是一个图,总用V(G)和E(G)分别表示图G的顶点集和边集,设X∈V(G),其邻点集Ⅳ()一{VlV∈V(G),V∈E(G)),又设x≤V(G),其邻点集Ⅳ(x)一UⅣ).1986年P.Fraisse推广了R.J.Fovdree等人的结论],证明了下列定理:定理AE设G是H阶的^一连通图,^≥2,若对于任意^一独立集S,有IN(S)1>=2^+l则G是HamiHonl图.众所周知,图G称为HamiHon一连通图,如果对于任意{X,Y)V(G),总有以X,Y为端点的HamiHon一路本文将类似于定理A,得到下
3、列定理:定理1设G是n阶^一连通图,^≥2若对于任意(^一1)一独立集s,有IⅣ(s)I>(^一1)—r一则G是HamiHon:连通图.根据Bondy的图论整性原则仿照田丰最近的一种方法,证明比定理1强的下列定理:定理2设G是一阶^一连通图,^≥2若对于任意^一独立集x一{X.,……X一),有●一1三lN(x{.))l>(^一1)n,则G是HamiHon一连通图.收稿日期:199203O2查起兆等:Hami]ton一连通图的一个充分条件l591定理2的证明在本文中,总将路看作有方向的,(,)一路Q总认为其方向是从z到,设是Q上的
4、二个顶点,且按其方向.先于,总用z.Qz.表示从沿着Q顺向到z.的路;用砭表示从z沿Q逆向到z的路.下面用反证法证明定理2成立.假设G满足定理2的条件,但不是HamiHon一连通图,则存在{".)(G),不存在以",为端点的HamiHon一路,设P为G中最长的(",)一路,则R—V(G)(P)≠,取.∈R,因G是愚一连通的.由Menger定理,存在以.为起点的k条路Q,Q"Q连通到V(尸),且这k条路除.外,其顶点两两不相交,不妨设(P)nV(Q.)=)(1,2,…k)+即Q为(工.,,Oq)一路,并且,,~2ooo以P的方向依次排列着,对
5、于i=1,2+…是一1,设工.为P上啡的后继顶点,令X一{.,.…,41),且设A—(G)Ⅳ(X),AP一n(P),A一nR(一(F)).B一{l∈V(G),存在唯一的{0,1,…,k一1),使口∈E(G)),B=BnV(P),且=BnR(一B(P)),D—(G)(UB),也就是为与x中任一顶点不相邻的所有顶点所组成的集合,B为恰与x中一个顶点相邻的所有顶点组成的集合,D为至少与x中两个顶点相邻的顶点所组成的集合.下面以一系列1理,来推得矛盾,从而证明定理的结论.^一1.引理1设Y∈(Q){q)(一1,2,…k一1),则每N(),从
6、而.每UN(z).证:用反证法,设yENCr.).便有比尸更长的(",)一路uPa.:户,矛盾.L理2x呈,从而,x为G的一独立集,且‰∈A.—l证:由引理1,.每UN(x.),于是,只要证明,对于任意i,J∈{1,2,…k～1)(<),有,E(G).用反证法,设xx∈E(G),便有比尸更长的(",)路,uPa..n,芦.P,矛盾.引理3设{,)x(<),则Ⅳ(.)nⅣ()nR一.从而,B一Rd一(G)(P)4.证:用反证法,设Y∈Ⅳ()nⅣ()nR.分两种情形讨论情形1当一0时,由引理1,Y每(Q),便有比P更长的(",)
7、一路uPa.P,矛盾.情形2当≠0时,不妨设<,由引理1Y每V(Q)UV(Q),便有比P更长的(",)路uPaodYxP口,矛盾.为了方便起见,设"∈V(P),用"表示沿着P方向的后一个顶点,此时≠V;用"表示沿着P方向的前一个顶点.引理4设0,≈∈X{z.)(<),则:(1)当"∈(uPa)时(表示路uPa上所有顶点所组成的集合),不能同时有"""∈E(G);(2)当∞∈V(~Pa)时,不能同时有∞什,∞∈E(G);(3)当∞∈(≈P)时,不能同时有"∞,∈E(G).证:(1)当=啦时,由引理2w'¨一每E(G)结论成立.l60
8、无锡轻工业学院第l2卷第2期当w≠时,用反证法,设WX,,W∈E(G),便有比P更长的h,口)一路uPwx.Pafljx.啦'P仉矛盾.(2)当—时由f理2,Wz=
