兩特殊圖類的相關(guān)圈問題.pdf

2、控制集(所含頂點的個數(shù)達(dá)到最小的控制集)中頂點的數(shù)目用γ(G)表示.當(dāng)γ(G)≤k時,G稱為k-控制的.記D(G)={v∈V(G):不連通},若D(G)是獨立集,而且 v∈D(G),局部連通u,使連通,則稱G是弱局部連通的;若D(G)是獨立集,而且 v∈D(G), u,使連通,則稱G是幾乎局部連通的.當(dāng)D(G)=φ時,G稱為局部連通.Hamilton問題是圖論研究的基本問題之一,主要集中在以下

3、兩個方面:圈問題及路問題,具體地講主要有:Hamilton圈問題、圈可擴問題,最長圈問題等以及Hamilton路問題,Hamilton連通問題,泛連通問題,路可擴性問題,最長路問題等,關(guān)于Hamilton圈的問題,已經(jīng)取得了長足的發(fā)展,1952年Dirac給出了圖中圈存在的最小度條件(稱為Dirac條件),1960年ore給出了度和條件(稱為ore條件),在很多條件下ore條件減弱了Dirac條件,得到了更好的論證,1984年,范更華在

4、[9]中給出了距離為2的點對中較大度條件(稱為Fan條件),由于直接研究任一圖類的Hamilton問題往往比較困難,于是人們轉(zhuǎn)而研究特殊圖類如無爪圖、幾乎無爪圖、擬無爪圖、距離無爪圖以及K<,1,P>約束圖等的Hamilton問題.關(guān)于無爪圖的路問題有如下一些結(jié)論:定理<'[2]>連通,局部2-連通的無爪圖是路可擴的定理<'[6]>設(shè)G為連通的無爪圖,則G有Hamilton路或長至少為2δ+2的路.定理<'[6]>設(shè)G為連通的無爪圖,|

5、G|=n,δ≥n-2/3,則G有Hamilton路.關(guān)于特殊圖類的Hamilton圈問題也有一些結(jié)論,該文對以下結(jié)果感興趣:定理A<'[10]>頂點數(shù)不小于3的連通,局部連通的無爪圖是哈密頓圖.后來許多圖論專家發(fā)現(xiàn)該定理的條件隱含著更強的圈性質(zhì),其中Hendry證明下面定理.定理B<'[3][11]>頂點數(shù)不小于3的連通,局部連通的無爪圖是完全圈可擴的.朱永津、王江魯證明了下面的定理定理C<'[29]>頂點數(shù)不小于3的連通,局部連通的K

6、<1,P>-約束圖是完全圈可擴的.定理D<'[30]>連通,幾乎局部連通的擬無爪圖是完全圈可擴的.受上述定理的啟發(fā),該文在弱局部連通以及幾乎局部連通的條件下,分別討論了K<,1,P>約束圖及強K<,1,P>約束圖的完全圈可擴性,它們分別推廣了定理C及定理D的結(jié)論.另外,距離無爪圖類作為特殊無爪圖類,該文感興趣的結(jié)果有:定理E<'[31]> G∈DC,G是2-連通的,則G有Hamilton路.定理F<'[31]> G∈DC,且G是3-連通

7、的,則G有Hamilton圖.我們在定理E、F的理論基礎(chǔ)上,研究了距離無爪圖在2-連通條件下的Hamilton圈問題.第一章中,我們主要介紹該論文所涉及的一些基本概念和符號.第二章中,我們給出了弱局部連通的定義,并在此條件下研究了K<,1,P>-約束圖的完全圈可擴,另外,在幾乎局部連通的條件下,研究了強K<,1,P>-約束圖的完全圈可擴,得到以下引理及定理:引理1<'[32]>對于K<,1,P>-約束圖而言,若圖C中存在局部連通點與圈外

8、點相鄰,則圈C有1-擴張.定理2.2<'[32]>頂點數(shù)≥3的連通,弱局部連通的K<,1,P>-約束圖是完全圈可擴的.定理2.3<'[33]>頂點數(shù)≥3的連通,幾乎局部連通,強K<,1,P>-約束圖是完全圈可擴的.在第三章中,提出另一個新禁用子圖--網(wǎng)全爪圖,該概念的提出是該章的創(chuàng)新點,得到如下定理:定理3.1<'[34]>2-連通的無網(wǎng)的距離無爪圖有Hamilton圈.定理3.2<'[34]> 2-連通的無網(wǎng)全爪的距離無爪圖有Hami