2-連通[4，2]-圖中的圈與高連通度圖的完全圈可擴(kuò)性.pdf

1、圖的哈密頓問題是圖論中一個十分重要且又十分活躍的研究課題，每年都有大量的關(guān)于這一問題的學(xué)術(shù)論文。1857年，愛爾蘭數(shù)學(xué)家哈密頓提出：“一個連通圖有哈密頓圈的充要條件是什么?”這樣一個問題。但是這個問題至今仍未能解決。后來人們發(fā)現(xiàn)它是一個NPC問題，于是降低要求間接研究該問題。與此同時，以Hamilton問題為出發(fā)點發(fā)展起了對圖的圈性質(zhì)的研究，這些性質(zhì)主要包括Hamilton性、泛圈性、完全圈可擴(kuò)性等。我們知道圖的完全圈可擴(kuò)性要比圖的泛圈

2、性更強(qiáng)，圖的泛圈性要比圖的哈密頓性更強(qiáng)，所以研究泛圈性和完全圈可擴(kuò)性就研究了圖的Hamilton性。關(guān)于哈密頓性的研究及最新進(jìn)展可見參考文獻(xiàn)[17]-[23]。關(guān)于泛圈性的研究及最新進(jìn)展可見參考文獻(xiàn)[24]-[34]，關(guān)于完全圈可擴(kuò)性的研究及最新進(jìn)展可見參考文獻(xiàn)[4]-[15]。對這些性質(zhì)的研究主要集中在兩方面，一方面是尋求這些圈性質(zhì)的充分條件，另一方面是研究某些特殊圖類的圈性質(zhì)。 本文主要討論了兩種特殊圖類中的圈性質(zhì)的問題。一

3、種圖類是[s,t]-圖，劉春房最早提出了[s，t]-圖的概念并進(jìn)行研究的。對[s，t]-圖的研究有著深刻的應(yīng)用價值，很典型的一個應(yīng)用就是在計算機(jī)的網(wǎng)絡(luò)配置上。另一種圖類是高連通度圖。這里的高連通度是指一個圖的連通度相對圖的階是較高的。當(dāng)一個圖的連通度足夠高時，這個圖可以保證圖的各種圈性質(zhì)，那么隨著圖的連通度的降低，圖的圈性質(zhì)將發(fā)生什么變化呢?本文就此討論了高連通度圖的完全圈可擴(kuò)性。為方便討論，在第三章中提出了s-點連通圖的概念，即連通度

4、為κ(G)=｜G｜-s+1的圖。在此基礎(chǔ)上主要討論了5-點連通圖，6-點連通圖的完全圈可擴(kuò)性，即連通度分別為|G|-4和|G|-5的高連通度圖的完全圈可擴(kuò)性。根據(jù)所得結(jié)果提出了s-點連通圖(κ(G)=|G|-s+1)在完全圈可擴(kuò)性方面的一個猜想。在第三章最后給出例子說明定理及猜想中對圖G的階的限制是最好可能的。 本文的主要內(nèi)容包括三章。在第一章中，我們主要介紹了文章中所涉及的一些概念、術(shù)語符號和本文的研究背景及已有的結(jié)果；在第二

5、章中，我們討論了2-連通[4，2]-圖中的圈；在第三章中，我們討論了高連通度圖的完全圈可擴(kuò)性并提出猜想。 我們得到的主要結(jié)果如下：定理2.1.1設(shè)G是2-連通[4，2]-圖，C是G中滿足|V(C)|＜|V(G)|的任一圈，則或者G中有(|C|+1)-圈，或者G同構(gòu)于K2，3，K1，1，3，F(xiàn)1，F(xiàn)2，F(xiàn)3，F(xiàn)4，F(xiàn)5。(其中F1，F(xiàn)2，F(xiàn)3，F(xiàn)4，F(xiàn)5如下圖)推論3.1.1設(shè)G為4-點連通圖且|G|≥7，則G是完全圈可擴(kuò)的。定理

6、3.1.1設(shè)G為5-點連通圖且|G|≥9，則G是完全圈可擴(kuò)的。定理3.1.1′設(shè)G滿足κ(G)=|G|-4且|G|≥9，則G是完全圈可擴(kuò)的定理3.1.2設(shè)G為6-點連通圖且|G|≥11，則G是完全圈可擴(kuò)的。定理3.1.2′設(shè)G滿足κ(G)=|G|-5且|G|≥11，則G是完全圈可擴(kuò)的。由上述定理提出下面的猜想猜想3.1.1設(shè)G為s-點連通圖且|G|≥2s-1，則G是完全圈可擴(kuò)的。 猜想3.1.1′設(shè)G滿足κ(G)=|G|-s+1