擬無(wú)爪圖和K-,1,2--擴(kuò)展圖的哈密頓問(wèn)題.pdf

1、圖的哈密頓問(wèn)題是圖論學(xué)科一個(gè)十分重要而且又十分活躍的研究課題，歷史也很悠久，每年都有大量關(guān)于這一問(wèn)題的學(xué)術(shù)論文.但是，由于直接研究一般圖類的哈密頓問(wèn)題比較困難，因此，當(dāng)前，圖的哈密頓問(wèn)題研究的一個(gè)重要方面是在一些特定領(lǐng)域展開(kāi).關(guān)于哈密頓問(wèn)題的一些研究進(jìn)展可參考[23]-[25].繼Beineke1968，1970年發(fā)表的[10]-[11]之后，人們開(kāi)始關(guān)注起包含著線圖的無(wú)爪圖.70年代末80年代初，是研究無(wú)爪圖的一個(gè)非?；钴S的時(shí)期，這一

2、時(shí)期，涌現(xiàn)了大量?jī)?yōu)秀的成果.其中，關(guān)于匹配性質(zhì)的可參考[12]-[14].較早關(guān)于無(wú)爪圖哈密頓性質(zhì)的可參考[15]-[18].關(guān)于多項(xiàng)式時(shí)間內(nèi)確定獨(dú)立數(shù)的可參考[19][20].關(guān)于Berge的完美圖猜想在無(wú)爪圖中的證明可參考[21].[22]是關(guān)于無(wú)爪圖的綜述性的文章，從中我們可了解到關(guān)于無(wú)爪圖的研究進(jìn)程.另外關(guān)于無(wú)爪圖中取得的優(yōu)秀成果的文章可參考[37]-[50].事實(shí)上，可跡性，泛圈性，完全圈可擴(kuò)性，哈密頓連通等這些之后提出的概念

3、本質(zhì)上都是對(duì)圖的哈密頓問(wèn)題的深層次的刻畫(huà). 最近若干年來(lái)，無(wú)爪圖的概念也被從不同角度推廣到了一些更大的圖類，如：半無(wú)爪圖，幾乎無(wú)爪圖，(K1,4；2)-圖，DCT圖等.其中，關(guān)于半無(wú)爪圖的一些研究進(jìn)展可參考[3]，[26]-[28],關(guān)于幾乎無(wú)爪圖的可參考文獻(xiàn)[29]-[32]，關(guān)于(K1,4；2)-圖的可參考[33]-[35].擬無(wú)爪圖是滕延燕，尤海燕2004年基于幾乎無(wú)爪圖在[6]中提出來(lái)的，它也是對(duì)無(wú)爪圖概念的一種推廣，但

4、它卻包含在幾乎無(wú)爪圖類中，然而，很多在幾乎無(wú)爪圖中很難研究的東西在擬無(wú)爪圖中卻比較容易找到方法來(lái)研究.(V)獨(dú)立集{x1，x2，…，xp}(∈)V(G)(p≥2)，如果N(x1)∩N(x2)∩…N(xp)≠φ，那么若(V)u∈N(x1)∩N(x2)∩…N(xp)，有N[u](∈)N[x1]∪N[x2]∪N[xp]，則稱u為{x1，x2，…，xp}的控制點(diǎn).否則，稱u為{x1，x2，…，xp}的非控制點(diǎn).{x1，x2，…，xp}的控制點(diǎn)組

5、成的集合稱為{x1，x2，…，xp}的控制集，記為D(x1，x2，…，xp)；{x1，x2，…，xp}的非控制點(diǎn)組成的集合稱為{x1，x2，…，xp}的非控制集，記為(D)(x1，x2，…，xp).(V)獨(dú)立集{x1，x2，…，xp}(∈)V(G)(p≥2)，如果N(x1)∩N(x2)∩…N(xp)≠φ，那么D(x1，x2，…，xp)≠φ，且若(V)u∈D(x1，x2，…，xp)，(V)v∈(D)(x1，x2，…，xp)，有uv∈E(G

6、)，則稱G為K1，p-擴(kuò)展圖.由定義不難知道K1,p1-free圖一定是K1,p-擴(kuò)展圖.特別地，K1,3-free圖一定是K1,2-擴(kuò)展圖.即易知K1,2-擴(kuò)展圖也是對(duì)無(wú)爪圖的一種推廣.這類圖是我們?cè)趯?duì)圖的結(jié)構(gòu)進(jìn)行深入研究的基礎(chǔ)上提出來(lái)的. 本篇論文中，我們主要研究了擬無(wú)爪圖的點(diǎn)泛圈性和不同連通條件下K1,2-擴(kuò)展圖的完全圈可擴(kuò)性. 在第一章中，我們主要介紹了文章中所涉及的一些概念，術(shù)語(yǔ)符號(hào)和本文的研究背景以及已有的一

7、些結(jié)果. 在第二章中，我們主要研究了擬無(wú)爪圖的點(diǎn)泛圈性，證明了下面兩個(gè)結(jié)果：定理2.2.3設(shè)G是連通的擬無(wú)爪圖且δ(G)≥3，若G中同構(gòu)于Z1的導(dǎo)出子圖有性質(zhì)φZ(yǔ)1(c，b1)或φz1(c，b2)，則G是點(diǎn)泛圈的(其中Z1如圖2.1中的圖). 定理2.3.3設(shè)G是2-連通的擬無(wú)爪圖且δ(G)≥3，若G中同構(gòu)于Z2的導(dǎo)出子圖有性質(zhì)φZ(yǔ)2(a1，b1)和φZ(yǔ)2(a1，b2)，則G是點(diǎn)泛圈的(其中Z2如圖2.2中的圖).

8、 事實(shí)上，以上兩個(gè)結(jié)果分別改進(jìn)了H.J.Broersma，H.J.Veldman[36]，MingchuLi[2]等人的相應(yīng)結(jié)果. 在第三章中，我們探討了不同條件下K1,2-擴(kuò)展圖的完全圈可擴(kuò)性，改進(jìn)了D.Oberly，D.Sumner[7]，L.Clark[8]以及G.R.T.Hendry[9]的相應(yīng)結(jié)果.得到了下面的三個(gè)定理：定理3.2.1設(shè)G是頂點(diǎn)數(shù)不小于3的連通的K1,2-擴(kuò)展圖，C為G中一r-圈(3≤r＜|V(G)|