幾類圖的路和圈性質.pdf

1、路和圈是圖的兩種基本結構，是分析和刻畫圖的有力工具，有大量的實際問題可以歸結為圖的路和圈問題，所以這方面一直是圖論中的熱點研究領域．關于路和圈的進展，已經取得了長足的發(fā)展，這方面的研究成果和進展可參見文獻[12]—[14]．事實上，圖論中三大著名難題之一的Hamilton問題本質上也是圖的路和圈問題．經過幾十年的發(fā)展，圖的路圈性質所涉及的內容日益豐富和具體．路的方面包括圖的Hamilton—路(可跡性)，最長路，Hamilton連通，泛

2、連通，路可擴等等；圈的方面包括圖的Hamilton圈，最長圈，(點)泛圈，完全圈可擴，點不交的圈，圈覆蓋等等。 由于直接研究一般圖的Hamilton問題往往比較困難，于是人們轉而研究不含有某些禁用子圖的圖類，繼Beineke1968，1970年發(fā)表的關于線圖性質的兩篇文章之后，人們開始關注包含著線圖的無爪圖．70年代末80年代初，是研究無爪圖的一個非常活躍的時期．關于無爪圖方面的部分優(yōu)秀成果可參考[1]—[3]，[17]—[22

3、]．[23]是關于無爪圖的綜述性的文章．另外，無爪圖的概念也被從不同角度推廣到了更大的圖類，如半無爪圖，幾乎無爪圖，(K1，4；2)—圖，DCT圖等．1994年，Z．Ryjacek定義了一種包含無爪圖的更大的圖類—幾乎無爪圖．之后，亦出現(xiàn)了不少研究這類圖的Hamilton問題的學術論文，如[28]—[30]．但事實上，無爪圖中很多很好的結果推廣到幾乎無爪圖難度非常大．所以，滕延燕，尤海燕2003年[4]在此基礎上提出了擬無爪圖的概念，它

4、包含無爪圖類但卻包含在幾乎無爪圖類中．這里，我們可以將半無爪圖，幾乎無爪圖，擬無爪圖統(tǒng)稱為類無爪圖。 2006年，曲曉英提出了K1，p—擴展圖的概念．我們在研究不同圖類結構的基礎上對K1，p—擴展圖的概念作了進一步的完善．{x1，x2，…，xp)∈V(G)(p≥2)是圖G中任意獨立集，若存在u∈N(x1)∩N(x2)∩．．．∩N(Xp)，使得N[u]∈()N[x1]∪N[x2]∪…∪N[xp]，則稱u為．[x1，x2，…，xp)

5、的擴展點，若存在v∈N(u)，v()N[x1]∪N[x2]∪…∪N[Xp]，稱u為{x1，x2，…，xp)的非擴展點．{x1，x2，…，xp}的擴展點組成的集合稱為{x1，x2，…，xp}的擴展點集，記為D(x1，x2，…，xp)；{x1，x2，…，xp)的非擴展點組成的集合稱為{x1，x2，…，xp)的非擴展點集，記為D(x1，X2，…，xp)．{x1，x2，…，xp)∈V(G)(p≥2)是圖G中任意獨立集，如果滿足D(x1，x2，…

6、，xp)≠φ，且()u∈D(x1，x2，…，xp)，()v∈—D(x1，X2，…，xp)，有uv∈E(G)，則稱G為K1，p—擴展圖．特別的，K1，2—擴展圖是包含著無爪圖類且比無爪圖類更大的圖類．我們深入的研究了K1，p—擴展圖的Hamiltorn性質及路可擴性。 對()v∈V(G)，若G[N(v)]是連通的，則稱v是G的一個局部連通的點．若G的任一點都是局部連通的點，則稱G是局部連通的．在局部連通的定義提出之后，張存全在19

7、89年提出了半局部連通的定義，研究了無爪圖在半局部連通條件下的一些性質．滕延燕和尤海燕在2002年定義了幾乎局部連通．而賴宏建在2004年提出了三角連通的概念，證明了無爪圖在三角連通下的一些結果．2008年，劉明穎提出了H—局部連通的概念，初步討論了H—局部連通下的無爪圖和半無爪圖的路圈性質．我們在此基礎上，討論了H—局部連通下擬無爪圖的一些性質，對H—局部連通下類無爪圖的性質進行了很好的完善。 本文主要研究了K1，p—擴展圖和

8、擬無爪圖在不同條件下的路圈性質。 在第一章中，我們主要介紹了本文的研究背景以及已有的一些結果，以及文章中所涉及的一些概念和術語符號。 在第二章中，我們具體討論了K1，p—擴展圖的Hamilton性質及路可擴性，得到下面兩個結果： 定理2.1.4連通的K1，2—擴展圖若滿足()x，y∈V(G)，—D(x，y)≠φ，則G有Hamilton路。 定理2.2.7 G是連通，局部2—連通的K1.2—擴展圖，P是G的

9、一條非Hamilton，路，()u，u∈Vp(x)(x∈V(G)—V(P))，若當u，v分別是x與其各自前點(或后點)的擴展點時，有u—v+，u+v—∈E(G)，則G是路可擴的。 在第三章中，我們通過具體實例討論了在不同局部連通條件下的擬無爪圖及擬無爪圖的圈可擴性，證明了下面的結果： 定理3.1.3三角連通的擬無爪圖是半局部連通的。 推論半局部連通的擬無爪圖的最小點割的階數(shù)至少是2。 定理3.2.4連通，

10、半局部連通，無網全爪的擬無爪圖是完全圈可擴的且無網全爪條件是必須的。 在第四章中，我們探討了H—局部連通的擬無爪圖的性質，Hamilton性質及圈可擴性，得到如下結果： 定理4.1.2階≥2m(m≥2)的連通，Km—局部連通擬無爪圖是2—連通。 定理4.1.4 G是K2—局部連通擬無爪圖，()xy∈E(G)，則G[N(xy)]中任意兩點間的最短路不超過6。 定理4.1.6設G是K3—局部連通擬無爪圖，G[