H-局部連通圖的路圈性質.pdf

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

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

3、]．[19]-[33]．[34]是關于無爪圖的綜述性的文章．另外．無爪圖的概念也被從不同角度推光到了更大的圖類．如半無爪圖．幾乎無爪圖．(K1.4:2)圖．DCT圖等．1998年．A.Ainouche在[7]中定義了一種包含無爪圖的更大圖類一半無爪圖且給出了關于半無爪圖的路和圈方面的一些結果．之后，很多專家學者相繼做了大量的工作來研究這類圖的Hamilton問題且將無爪圖中的許多非常好的結果推廣到了半無爪圖．其中某些進展可參考[35]-

4、[37]．1994年，Z．Rgjacek定義了一種包含無爪圖的更大的圖類-幾乎無爪圖．之后,亦出現(xiàn)了不少研究這類圖的Hamilton問題的學術論文如[39]-[41]． 對τ∈ V(G)．若G[N(v)]是連通的,則稱v是G的一個局部連通的點．若G的任一點都是局部連通的點．則稱G是局部連通的．在局部連通的定義提出之后．張存全在1989年提出了半局部連通的定義，研究了無爪圖在半局部連通條件下的一些性質．滕延燕和尤海燕在2002年定

5、義了幾乎局部連通．而賴宏建在2004年提出了三角連通的概念，證明了無爪圖在三角連通下的一些結果．曲曉英又把這些結果推廣到了半無爪圖和擬無爪圖．我們是在他們的啟發(fā)下提出的H-局部連通的概念．初步討論了K2-局部連通下無爪圖的一些性質．人們相繼又提出了許多不同的相關定義如：幾乎局部連通、半局部連通、三角連通、2-階鄰域連通等．H-局部連通圖是我們在研究不同圖類結構的基礎上所提出的一種新的圖類。 Zden(e)k．Ry(jac)ek在1997

6、年提出了閉包的概念．并解決了無爪圖中的一系列Ha-milton問題．Zden(e)k．Ry(jac)ek所定義的閉包著眼于對局部連通的點的鄰域增加邊．H．J.Broersma和Tromme]先后又提出了K4-閉包和K*4閉包。RomanCada在2001年提出了C4-閉包和C5-閉包．本文在他們的啟發(fā)下定義了兩種閉包K2-閉包和K2-閉包．并且初步討論了無爪圖和半無爪圖在這兩種閉包下的一些性質． 本篇論文主要研究了K2-局部連通

7、下無爪圖和半無爪圖的路和圈問題,以及無爪圖和半無爪圖在我們定義的兩種新閉包下的一些性質． 在第一章中．我們主要介紹了本文的研究背景以及已有的一些結果,以及文章中所涉及的一些概念和術語符號． 在第二章中．我們具體討論了H-局部連通圖的一些性質. 在第三章中,我們研究了K2-局部連通圖的圈可擴性,證明了下面的結果: 完成K2-局部連通的無爪圖Hamilton性的證明之后．我們開始考慮它的圈可擴性．我們發(fā)現(xiàn)這一