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

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

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

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

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

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

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

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