禁用子圖與圖的路圈性質(zhì).pdf

1、路和圈是圖的兩個基本結(jié)構(gòu)，是分析、刻畫圖的整體結(jié)構(gòu)的有力工具.大量的實際問題都可以歸結(jié)為圖的路和圈的問題.對圖的路圈性質(zhì)的研究是在圖論中的著名問題——哈密頓問題的基礎(chǔ)上發(fā)展而來的.關(guān)于圖的哈密頓圈的研究，已經(jīng)取得了長足的發(fā)展，這方面的研究成果和進展情況可參見文獻.對圖的路和圈性質(zhì)的研究一直是圖論中的熱門領(lǐng)域，經(jīng)過幾十年的發(fā)展，圖的路圈性質(zhì)所涉及的內(nèi)容日益豐富和具體。路的方面包括圖的哈密頓路(可跡性)、最長路、Hamilton連通、泛連通

2、、路可擴等等；圈的方面包括圖的哈密頓圈、最長圈、(點)泛圈、完全圈可擴等等. 由于直接研究一般圖的路圈性質(zhì)比較困難，若干年來相關(guān)的研究主要集中在一些特殊圖類上，即不含某些禁用子圖的圖類.其中比較有代表性的是無爪圖，它是以K1，3為禁用子圖的圖類，研究該圖類的最初動機來源于Deineke所給的線圖的性質(zhì)[8][9]，上個世紀(jì)八九十年代對無爪圖的研究成為圖論中的著名課題，至今在這方面已取得了相當(dāng)多的研究成果.在此基礎(chǔ)上，人們將研究圖

3、類逐漸拓寬至幾乎無爪圖、爪心獨立圖、半無爪圖、(K1，p；q)-圖等等.這些圖類或是無爪圖的推廣，或與無爪圖有密切聯(lián)系，近年來其它一些新型的禁用子圖也不斷被提出.本文就是研究某些禁用子圖與圖的路圈性質(zhì). 第一章主要介紹本文的研究背景和相關(guān)結(jié)論，以及文章所涉及到的一些基本概念和術(shù)語符號. 第二章主要研究半無爪圖的可跡性.這一章分為四個小節(jié)，在§2.1節(jié)介紹了半無爪圖的概念和研究成果，§2.2，§2.3，§2.4節(jié)分別給出了

4、本章的三個主要定理.引理2.2.1設(shè)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設(shè)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

5、)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設(shè)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

6、階3-連通半無爪圖，滿足NC≥2n-5/3，則圖G是齊次可跡的. 定理2.4若G為n階2-連通半無爪圖，滿足NC≥2n-4/3，則圖G是齊次可跡的. 第三章主要研究(K1,p；q)-圖(p=4，q=1，2)的路性質(zhì).這一章分為三個小節(jié)，§3.1節(jié)主要介紹(K1，p；q)-圖的概念及研究狀況，§3.2節(jié)研究(K1，4；1)-圖的3-walk，§3.3節(jié)研究(K1,4；2)-圖的路可擴性，所得到的主要定理如下： 引理

7、3.2.1設(shè)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-fre

8、e圖都有一個3-walk. 推論3.2.4在連通的K1,4-free圖中，如果存在一個coveringwalk通過x點n(n≤3)次，那么一定存在一個3-walk通過x點n次. 論斷3.2.5設(shè)G是連通的K1，4-free圖，x∈V(G)，則存在一個3-walkC使得V(x，C)=1當(dāng)且僅當(dāng)x不是G的割點. 由論斷3.2.3和推論3.2.5可得：定理3.2.6連通的k1.4-free圖存在一個3-walk，并且對

9、x∈V(G)存在一個3-walk通過x恰好一次當(dāng)且僅當(dāng)x不是G的割點. 定理3.3.4設(shè)G是連通，局部2-連通的(K1,4；2)-圖，|G|≥7，δ≥3，則G是路可擴的. 第四章研究爪心獨立圖和T3-受限圖的圈性質(zhì).這兩類圖都是和無爪圖有密切聯(lián)系的圖，其中T3-受限圖是本文所定義的一類新圖.§4.1節(jié)研究爪心獨立圖的模k泛圈性，§4.2節(jié)研究T3-受限圖的Hamilton性質(zhì)，所得到的主要定理如下： 定理4.1.