Y-,3-V-,3--free圖的哈密爾頓問題.pdf

1、哈密爾頓問題一直是圖論中近幾年來研究的一個熱點，這從國際上幾種著名的數學刊物及國內幾種核心數學期刊發(fā)表的文章可見一斑。判斷一個圖在什么條件下是一個哈密爾頓圖即所謂的哈密爾頓問題。而禁用子圖的哈密爾頓問題是哈密爾頓問題研究重要的研究領域之一。無爪圖(claw-free graphs)是禁用子圖研究最為深入的一個圖類。關于無爪圖的哈密爾頓問題，目前已有很多出色的且較為成熟的結果。同時與無爪圖相關的且比無爪圖更廣的圖類-如幾乎無爪圖(almo

2、stclaw-free graphs)、半無爪圖(quasi-ckaw-free graphs)的研究更是方興未艾，新的結果層出不窮。 本文采用“強思維”與“弱思維”的方式首次研究了一種比無爪圖更廣的圖類Y<,3>V<,3>-free圖的哈密爾頓問題，這些結果拓展了哈密爾頓問題的研究。 首先本文在第二章第一節(jié)研究了在連通、局部連通條件下Y<,3>V<,3>-free圖的哈密爾頓性。在連通局部連通條件下存在Y<,3>V<,

3、3>-free圖是非哈密爾頓圖；甚至存在連通度、局部連通度任意大的Y<,3>V<,3>-free非哈密爾頓圖。圖的最長圈的研究常常會促進圖的哈密頓性的研究。進一步研究Y<,3>V<,3>-free圖的最長圈得到本文的第一個重要結果(第二章第一節(jié))：定理 1.1.1 若G是頂點數不小于3的連通、局部連通Y<,3>V<,3>-free圖，則G的最長圈為控制圈，且G是局部泛圈圖(subpancyclic graphs)。 本文在第二

4、章第二節(jié)接著探討在連通局部連通條件下Y<,3>V<,3>-free圖成為哈密爾頓圖的條件。得到了下面的結果(第二章第一節(jié))：定理2.1.2頂點數不小于3的連通、局部連通Y<,3>V<,3>-free、爪心獨立圖是完全圈可擴的。并得到了下面的兩個推論：推論 2.1.1頂點數不小于3的連通、局部連通Y<,3>V<,3>-free、幾乎無爪圖是完全圈可擴的。推論2.1.3頂點數不小于3的連通、局部連通Z<,1>-free、幾乎無爪圖圖是完全圈

5、可擴的。 這些定理與推論是本文的第二個重要結果，它給出了幾乎無爪圖是完全圈可擴圖的兩個充分條件，比較經典的充分條件是Zdenek Ryjacek給出的，見下面的定理：定理若G是頂點數不小于3的連通、局部連通K<,1,4>-free、幾乎無爪圖則G是完全圈可擴圖。 閉包方法是解決哈密爾頓問題的重要手段和方法。本文最重要的創(chuàng)造性工作在于一種無爪圖閉包的構造及一種Y<,3>V<,3>-free圖類的閉包構造與穩(wěn)定性討論。在97

6、年Zdenek Ryjacek定義了無爪圖中的一種閉包概念，解決了無爪圖中的一系列哈密爾頓問題。設計一種無爪圖中比Zdenek Ryjacek閉包更多邊的閉包是哈密爾頓問題閉包研究一個努力的方向。Zdenek Ryjiacek閉包的構造著眼于局部連通點增加邊。本文在此基礎上同時著眼于一定條件下的局部不連通點，構造了一種無爪圖中比Zdenek Ryjacek定義的閉包更強(增加更多邊)的閉包，并證明了保持周長不變且是唯一的。本文的第三章