P3-支配圖的若干路圈性質(zhì).pdf

1、本文對(duì)P3-支配圖的若干路圈性質(zhì)進(jìn)行了探討。圖論作為現(xiàn)代數(shù)學(xué)的重要分支之一，在城市規(guī)劃，信息傳輸，電氣網(wǎng)路等方面的應(yīng)用越來(lái)越廣泛．圖的兩種基本結(jié)構(gòu)是路和圈，它們是分析和刻畫圖的有力工具，有大量的實(shí)際問(wèn)題可以歸結(jié)為圖的路和圈問(wèn)題．所以這方面一直是圖論中一個(gè)十分重要而且活躍的研究課題。事實(shí)上，圖論中三大著名難題之一的Hamilton問(wèn)題本質(zhì)上也是圖的路和圈問(wèn)題。國(guó)內(nèi)外許多學(xué)者對(duì)此問(wèn)題作了大量的研究工作．這方面的研究成果和進(jìn)展可參見文獻(xiàn)[28

2、]-[32]。其中度條件和鄰域并條件成為研究路和圈問(wèn)題的重要途徑，在這方面取得了很多優(yōu)秀的成果。經(jīng)過(guò)幾十年的發(fā)展，圖的路圈性質(zhì)所涉及的內(nèi)容日益豐富和具體．路的方面包括圖的Hamliton路(可跡性)，齊次可跡性，最長(zhǎng)路，Hamilton-連通，泛連通，路可擴(kuò)等等；圈的方面包括圖的Hamilton圈，最長(zhǎng)圈，(點(diǎn))泛圈，完全圈可擴(kuò)，點(diǎn)不交的圈，圈覆蓋等等。由于直接研究一般圖的Hamilton問(wèn)題往往比較困難，于是人們轉(zhuǎn)而研究不含有某些禁用

3、子圖的圖類，例如無(wú)爪圖。繼Beineke1970年發(fā)表的關(guān)于線圖性質(zhì)的文章[4]之后，人們開始關(guān)注包含著線圖的無(wú)爪圖．70年代末80年代初，是研究無(wú)爪圖的一個(gè)非常活躍的時(shí)期．關(guān)于無(wú)爪圖方面的部分優(yōu)秀成果可參考[1]-[3]，[10]-[22]．另外，無(wú)爪圖的概念也被從不同角度推廣到了更大的圖類，半無(wú)爪圖，幾乎無(wú)爪圖，(K1,4；2)-圖等．其中，1998年，A．Ainouche提出半無(wú)爪圖的概念，使許多無(wú)爪圖的結(jié)果可以推廣到半無(wú)爪圖，并