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

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

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

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