若干H-局部連通圖的路和圈問題.pdf

1、路和圈是圖的兩種基本結(jié)構(gòu)，是分析和刻畫圖的有力工具，有大量的實(shí)際問題可以歸結(jié)為圖的路和圈問題．所以圖的路和圈問題是圖論中一個(gè)十分重要而且活躍的研究課題．圖論中三大著名難題之一的Hamilton問題本質(zhì)上也是圖的路和圈問題．國(guó)內(nèi)外許多學(xué)者對(duì)此問題作了大量的研究工作．這方面的研究成果和進(jìn)展可參見文獻(xiàn)[38][42]經(jīng)過幾十年的發(fā)展，圖的路圈性質(zhì)所涉及的內(nèi)容日益豐富和具體．路的方面包括圖的Hamilton路(可跡性)，齊次可跡性，最長(zhǎng)路，Ha

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

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

4、成果可參見文獻(xiàn)[8][10]．連通和局部連通是研究圖的路圈性質(zhì)的常用條件，在局部連通的概念提出之后，張存全在1989年提出了半局部連通的定義，并研究了無爪圖在半局部連通條件下的一些性質(zhì)．之后人們又相繼提出了許多不同的相關(guān)定義，如：幾乎局部連通，三角連通，2-階鄰域連通等．2008年劉明穎提出了H-局部連通圖的概念，并初步討論了K2-局部連通條件下無爪圖的一些性質(zhì)．本文在此基礎(chǔ)上進(jìn)一步研究若干種圖類，如無爪圖、(K1,4；2)-圖、[5，