论文部分内容阅读
路和圈是图的两个基本结构，是分析、刻画图的整体结构的有力工具.大量的实际问题都可以归结为图的路和圈的问题.对图的路圈性质的研究是在图论中的著名问题——哈密顿问题的基础上发展而来的.关于图的哈密顿圈的研究，已经取得了长足的发展，这方面的研究成果和进展情况可参见文献.对图的路和圈性质的研究一直是图论中的热门领域，经过几十年的发展，图的路圈性质所涉及的内容日益丰富和具体。路的方面包括图的哈密顿路(可迹性)、最长路、Hamilton连通、泛连通、路可扩等等；圈的方面包括图的哈密顿圈、最长圈、(点)泛圈、完全圈可扩等等.
由于直接研究一般图的路圈性质比较困难，若干年来相关的研究主要集中在一些特殊图类上，即不含某些禁用子图的图类.其中比较有代表性的是无爪图，它是以K1，3为禁用子图的图类，研究该图类的最初动机来源于Deineke所给的线图的性质[8][9]，上个世纪八九十年代对无爪图的研究成为图论中的著名课题，至今在这方面已取得了相当多的研究成果.在此基础上，人们将研究图类逐渐拓宽至几乎无爪图、爪心独立图、半无爪图、(K1，p；q)-图等等.这些图类或是无爪图的推广，或与无爪图有密切联系，近年来其它一些新型的禁用子图也不断被提出.本文就是研究某些禁用子图与图的路圈性质.
第一章主要介绍本文的研究背景和相关结论，以及文章所涉及到的一些基本概念和术语符号.
第二章主要研究半无爪图的可迹性.这一章分为四个小节，在§2.1节介绍了半无爪图的概念和研究成果，§2.2，§2.3，§2.4节分别给出了本章的三个主要定理.引理2.2.1设G是n阶连通半无爪图，P是一条长为r的路(3≤r＜n)，如果G不含长为r+1的路，则对()ux∈E(V(P)，V(G)-V(P))，有u-u+∈E(G).
引理2.2.2设G是n阶连通半无爪图，P是G的一条最长路(|P|＜n)，H是G-P的一个连通分支，ux，uy∈E(V(P)，V(H))(u，v∈V(P)；x，y∈V(H))，那么(a)u(){v-，v-2，v-3，v+，v+2，v+3}(b)v-，u+，v-2，v+2()N(u)(c)E({u-，u-2}，{u-，u-2})=Φ=E({u+，u+2}，{v+，v+2}).
定理2.2.3若G为n阶2-连通半无爪图，满足NC≥n-2/2，则G是可迹的.
引理2.3.1设G是连通半无爪图，u∈V(G)，P是G中一条最长的v-的路，ux∈E(V(P)-{v}，V(G-P))(u∈V(P)，x∈V(G-P))，则u-u+∈E(G).
定理2.3.2若G为n阶3-连通半无爪图，满足NC≥2n-5/3，则图G是齐次可迹的.
定理2.4若G为n阶2-连通半无爪图，满足NC≥2n-4/3，则图G是齐次可迹的.
第三章主要研究(K1,p；q)-图(p=4，q=1，2)的路性质.这一章分为三个小节，§3.1节主要介绍(K1，p；q)-图的概念及研究状况，§3.2节研究(K1，4；1)-图的3-walk，§3.3节研究(K1,4；2)-图的路可扩性，所得到的主要定理如下：
引理3.2.1设G是一个K1,4-free图，x∈V(G)，C是G的一个coveringwalk.如果V(x，C)≥4，则存在一个coveringwalkC′使得l(C′)≤l(C)-1，V(x，C′)=V(x，C)-1并且对任意的y∈V(G)(y≠x)有u(y，C′)≤V(y，C).
推论3.2.2每一个连通的K1，4-free图的最小coveringwalk是一个3-walk.
推论3.2.3每一个连通的K1,4-free图都有一个3-walk.
推论3.2.4在连通的K1,4-free图中，如果存在一个coveringwalk通过x点n(n≤3)次，那么一定存在一个3-walk通过x点n次.
论断3.2.5设G是连通的K1，4-free图，x∈V(G)，则存在一个3-walkC使得V(x，C)=1当且仅当x不是G的割点.
由论断3.2.3和推论3.2.5可得：定理3.2.6连通的k1.4-free图存在一个3-walk，并且对x∈V(G)存在一个3-walk通过x恰好一次当且仅当x不是G的割点.
定理3.3.4设G是连通，局部2-连通的(K1,4；2)-图，|G|≥7，δ≥3，则G是路可扩的.
第四章研究爪心独立图和T3-受限图的圈性质.这两类图都是和无爪图有密切联系的图，其中T3-受限图是本文所定义的一类新图.§4.1节研究爪心独立图的模k泛圈性，§4.2节研究T3-受限图的Hamilton性质，所得到的主要定理如下：
定理4.1.42-连通的爪心独立图G，如果任意的非爪心点v都满足d(v)≥k+1，任意的爪心点u都有u∈N(u)使得d(u)≥k+2，那么图G是模k点泛圈的.
定理4.2.1G是2-连通非Hamilton的T3-受限图当且仅当G∈F′={KtVH：H是Km的支撑子图，2≤m＜t}
推论4.2.2设图G是n阶2-连通T3-受限图，W是G的最大独立集，如果|NG(W)|≥n/2，则G是Hamilton的.