幾類圖的路和圈性質(zhì).pdf

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

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

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

4、包含無爪圖類但卻包含在幾乎無爪圖類中．這里，我們可以將半無爪圖，幾乎無爪圖，擬無爪圖統(tǒng)稱為類無爪圖。 2006年，曲曉英提出了K1，p—擴(kuò)展圖的概念．我們?cè)谘芯坎煌瑘D類結(jié)構(gòu)的基礎(chǔ)上對(duì)K1，p—擴(kuò)展圖的概念作了進(jìn)一步的完善．{x1，x2，…，xp)∈V(G)(p≥2)是圖G中任意獨(dú)立集，若存在u∈N(x1)∩N(x2)∩．．．∩N(Xp)，使得N[u]∈()N[x1]∪N[x2]∪…∪N[xp]，則稱u為．[x1，x2，…，xp)

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

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

7、89年提出了半局部連通的定義，研究了無爪圖在半局部連通條件下的一些性質(zhì)．滕延燕和尤海燕在2002年定義了幾乎局部連通．而賴宏建在2004年提出了三角連通的概念，證明了無爪圖在三角連通下的一些結(jié)果．2008年，劉明穎提出了H—局部連通的概念，初步討論了H—局部連通下的無爪圖和半無爪圖的路圈性質(zhì)．我們?cè)诖嘶A(chǔ)上，討論了H—局部連通下擬無爪圖的一些性質(zhì)，對(duì)H—局部連通下類無爪圖的性質(zhì)進(jìn)行了很好的完善。 本文主要研究了K1，p—擴(kuò)展圖和

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

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

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