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

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

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

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

4、它卻包含在幾乎無爪圖類中，然而，很多在幾乎無爪圖中很難研究的東西在擬無爪圖中卻比較容易找到方法來研究.(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ò)展圖也是對無爪圖的一種推廣.這類圖是我們在對圖的結(jié)構(gòu)進(jìn)行深入研究的基礎(chǔ)上提出來的. 本篇論文中，我們主要研究了擬無爪圖的點(diǎn)泛圈性和不同連通條件下K1,2-擴(kuò)展圖的完全圈可擴(kuò)性. 在第一章中，我們主要介紹了文章中所涉及的一些概念，術(shù)語符號和本文的研究背景以及已有的一

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

8、 事實(shí)上，以上兩個結(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é)果.得到了下面的三個定理：定理3.2.1設(shè)G是頂點(diǎn)數(shù)不小于3的連通的K1,2-擴(kuò)展圖，C為G中一r-圈(3≤r＜|V(G)|