H-局部連通圖的路圈性質(zhì).pdf

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

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

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

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

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

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

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