[s,t]-圖的若干路圈性質(zhì).pdf

1、圖的路和圈問(wèn)題是圖論中一個(gè)十分重要而且活躍的研究課題，有大量的實(shí)際問(wèn)題可以歸結(jié)為圖的路和圈問(wèn)題．圖論中三大著名難題之一的Hamilton問(wèn)題本質(zhì)上也是圖的路和圈問(wèn)題．國(guó)內(nèi)外許多學(xué)者對(duì)此問(wèn)題作了大量的研究工作．這方面的研究成果和進(jìn)展可參見(jiàn)文獻(xiàn)[38]-[42]．其中度條件和鄰域并條件成為研究路和圈問(wèn)題的重要途徑，在這方面取得了很多優(yōu)秀的成果．經(jīng)過(guò)幾十年的發(fā)展，圖的路圈性質(zhì)所涉及的內(nèi)容日益豐富和具體．路的方面包括圖的Hamilton路(可跡

2、性)，齊次可跡性，最長(zhǎng)路，Hamilton連通，泛連通，路可擴(kuò)等等；圈的方面包括圖的Hamilton圈，最長(zhǎng)圈，(點(diǎn))泛圈，完全圈可擴(kuò)，點(diǎn)不交的圈，圈覆蓋等等．
　　由于直接研究一般圖的Hamilton問(wèn)題往往比較困難，于是人們轉(zhuǎn)而研究不含有某些禁用子圖的圖類．繼Beineke1970年發(fā)表的關(guān)于線圖性質(zhì)的文章[17]之后，人們開(kāi)始關(guān)注包含著線圖的無(wú)爪圖．70年代末80年代初，是研究無(wú)爪圖的一個(gè)非常活躍的時(shí)期．關(guān)于無(wú)爪圖方面的部分

3、優(yōu)秀成果可參考[1]-[3]，[19]-[31]．另外，無(wú)爪圖的概念也被從不同角度推廣到了更大的圖類，半無(wú)爪圖，幾乎無(wú)爪圖，(K1,4；2)-圖等．
　　2005年，劉春房在[4]中定義了一種新的圖類-[s，t]-圖，即任意s個(gè)點(diǎn)之間至少含有t條邊．程建民在[s，t]-圖的基礎(chǔ)上提出了強(qiáng)-[s，t]圖[51]的概念，即任意s個(gè)點(diǎn)之間至少含有t條獨(dú)立邊．[s，t]-圖的特點(diǎn)是其邊的分布比較均勻，因而在交通網(wǎng)絡(luò)，通信系統(tǒng)，計(jì)算機(jī)的網(wǎng)絡(luò)

4、配置等方面有著很典型的應(yīng)用．
　　本文就是研究[s,t]-圖的若干路圈性質(zhì). 在第一章中,我們主要介紹文章中所涉及的一些概念和術(shù)語(yǔ)符號(hào),以及本文的研究背景和已有的一些結(jié)果. 在第二章中,我們主要研究了[s,t]-圖在不同條件下的路圈性質(zhì),得到下面的結(jié)果：定理2.1.3設(shè)G是k-連通[k+2,2]-圖(k≥2),則G或者含有Hamilton圈或者同構(gòu)于Petersen圖或者同構(gòu)于Kk+1∨Gk(其中Gk是含有k個(gè)點(diǎn)的任意圖). 推論

5、2.1.3設(shè)G是k-連通[k+2,2]-圖(k≥2)且|G|≥2k+2,則G含有Hamilton圈. 定理2.2.4設(shè)G是k-連通[k+3,2]-圖(k≥1),則G或者含有Hamilton路或者同構(gòu)于Kk+2∨Gk(其中Gk是含有k個(gè)點(diǎn)的任意圖). 推論2.2.4設(shè)G是k-連通[k+3,2]-圖(k≥1)且|G|≥2k+3,則G含有Hamilton路.在第三章中,討論了2-連通[4,2]-圖中的泛圈,得到了下面的結(jié)果：定理3.2設(shè)G是δ