图的Hamilton性的几个充分条件

《图的Hamilton性的几个充分条件》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、贵州大学硕士学位论文图的Hamilton性的几个充分条件姓名：张扬申请学位级别：硕士专业：基础数学指导教师：曹义20030501摘要设G是一个图．称G是Hamilton图，如果G中含有Hamilton圈．称G是卜H鲫ilton图，如果对于任意的“∈矿(G)，G一协)是HaIⅡ“ton图．称G是Hal珏ilton一连通图。妇果对于任意的恤，v}￡y(G)，G中最长的(“，v)路是H鲫ilton路．本文利用[17]中给出的插点引理，借助图G的部分平方图G‘中的(七+1)个顶点的独立集的子集的邻域，给出与女有关的卜连通图的Hamilton性的几个充分条件．在下列定理中，假设y={_)，。，M，⋯，

2、y。)∈，¨(G’)，对于任意的f∈∞，l，2，⋯，女}(这里咒的下标将取模七}1)，r={咒，y。，⋯，，0(¨1)￡F定理A设G是一个≈一连通图。☆≥2；6是一个整数，并且O<6<女+1．当1(6<量时，掣=l：当6=1或足时，卢=O如果对于任意的】r∈，㈧(G+)，在G中有：帼=扣驯>半㈨y)_1)+掣，则G是HaIIlilton图．推论^设G是一个t～连通图，女≥2，6是一个整数，1<6之t．并且月(J，)足够大(即月(y)≥6(2女～6+1)+1)．如果对于任意的y∈，。(G+)，在G中有：％(y)：圭IⅣ(I)p垃岩(n(】，)一1){-O-则G是Halnilton图定理B设G是

3、一个(^+1)一连通图，≈≥2，6是一个整数o<6<七+1，当l<6<七时，Ⅳ=l；当6=1或≈时，-=o如果对于任意的yEt+．(G‘)，在G中有：州_y)：圭fⅣ(枷半彬)+趔竽业l‘O‘。则G是1_Hamilton图．推论8设G是一个(七+1)一连通图，女≥2，6是一个整数-1<6<七?并且月(y)足够大(即”(y)≥6(2七一6十1))．如果对于任意的y∈，¨(G+)，在G中有：吒(】，)：杰lⅣ(I)p霉净咿)扫0-则G是卜H锄ilton图．定理c设G是一个(女+1)一连通图，女≥3：6是一个整数，0<6<七+I．当l<6<七时，∥；1：当6=l或七时，卢=0如果对于任意的y∈‘+

4、。(G‘)，在G中有：吼(y)：壹IⅣ(驯>半彬)+避掣业f-O‘则G是HaIIlilton一连通图．推论C设G是一个(豇+1)一连通图，七≥2，6是一个整数且1<6<七：H(y)足够大(即n(】，)≥6(2七一6+1))，如果对于任意的】，∈L+。(G’)，在G中有：删=喜

5、Ⅳ(驯>半咿)则G是HaIIlilton一连通图．关键词：HaJIlilton性，部分平方图，插点．1．1概念符号第一章引言本文中末加楚义的符号和术语参见[11]，本文仅考虑有限简单图，在本节介绍文中将要使用的一些定义和符号．设G是一个图，iy(G)I称为G的阶，在一个图G中，包含G的每个顶点的路称为G的H硼jIton

6、路：类似地，G的H硼．1ton圈是指包含G的每／卜顶点的圈．而一个图若包含HalIIilton圈，则称这个图是Hamilton圈．不含H鲫ilton圈的图称为非H硼iIton图．称G是卜H鲫ilton图，如果对于任意的H∈矿(G)，G一{“)是Hamilton图．如果对于任意的伽，v}￡矿(G)，G中最长的(“，v)路是HalIlilton路，则G为H蛳IIton．连通图．图G中的圈c称为极大圈，如果不存在G中的圈C’，使得联c’)3y(c)．部分平方图G+是满足下列条件的图：矿(G‘)=矿(G)，且E(G‘)=E(G)U{工l石2：石l工2萑E(G)，且．，(工．，z2)≠妒}，其中以‘，

7、x2)=忸：ⅣgⅣ(而)nⅣ(z：)'Ⅳ国)∈Ⅳ(玉)UⅣO：)U{五，叠})．称5为G的一个独立集，如果s是矿(G)的一个子集，且S中任意两个顶点在G中互不相邻．，，(G)={z：Z是独立集，fZ

8、=f}(f是正整数)1．2一些相关的已知结果H硼ilton问题是图论的基本问题之一，它的历史可以追溯到1850年．到目前为止，人们已经从许多方面对这一问题进行了研究，得到了大量深刻的结果，并提出了一些新的课题．本节简列一些相关的已知结果．本文总设G是一个图，}矿(G)障3．定理1川设G是n阶图．若占(G)≥昙，则G是H硼ilton图．定理2m1设G是n阶图．若对每个z∈，：(G)，有∑d(：)≥

9、n：tZ则G是Hamilton图．定理2推广了定理1．定理3州设G是一个图，口(G)是G独立数，七(G)是G的连通度若口(G)≤Jf(G)，贝0G是H锄ilton图定理4‘”1设G是n阶

10、i}-连通图，七≥2．若对任意的z∈‘+。(G)有：弘)>盟P，则G是Hmih∞图定理5吲设G是n阶2一连通图，若对于任意的zg厶(G)，有∑d(z)≥n+t(G)，=eZ则G是Hamilton图定理6”1设G是^阶2一连通