乘積圖的可擴性與(n,k,d)-圖.pdf

1、圖的可擴性是圖論中一個有意義的研究分支．Sunmer在1979年提出是否可以對擁有“每一個匹配均可擴展成一完美匹配”性質(zhì)的圖類進行刻畫。如果將這一性質(zhì)略加放松，要求對擁有相同邊數(shù)的匹配擴展成一完美匹配，就得到了上述圖類的一種有趣的加細—k-可擴圖，這一概念由Plummer授在1980年提出．
　　 對k-可擴圖以及它的深刻推廣—n-因子臨界圖的性質(zhì)的描述，是可擴圖研究的重點．1995年，Chan、Chen和于青林教授證明了阿貝爾

2、群上連通凱萊圖是2-可擴的．受此啟發(fā)，本論文第一部分討論了雙循環(huán)群上任意連通凱萊圖的可擴性，并證明了圖的字典積可擴性定理。
　　 注意到可擴性與因子臨界性具有相似特性，自然考慮是否能將兩者結(jié)合的問題。2001年，劉桂真教授和于青林教授結(jié)合匹配缺失性、n-因子臨界性以及k-可擴性的概念提出了(n，k，d)-圖，并給出了一個圖是（n，k，d）-圖的充分必要條件。在論文的第二部分，我們將研究(n，k，d）-圖的遞推關(guān)系，極圖以及堅韌度

3、和綁定數(shù)參數(shù)的性質(zhì)。最后，我們給出極大非-（n，k，d)-圖的結(jié)構(gòu)定理。
　　 對于正則圖的正則因子存在性問題，Petersen首先證明了無邊割的3-正則圖存在1-因子，此后，Tutte得到了k-因子存在的充分必要條件．本論文的第三部分給出了偶正則點刪除子圖存在k-因子的充分條件。
　　 論文結(jié)構(gòu)如下：
　　 第一章，介紹圖論中的一些基本概念、術(shù)語、符號以及乘積圖與（n，k d)-圖的基本知識，此外，我們也介紹一

4、些有關(guān)因子存在性、可擴圖和因子臨界圖的著名定理。
　　 第二章，主要討論雙循環(huán)群凱萊圖的可擴性和可擴圖的字典積。在第一節(jié)，我們證明了雙循環(huán)群下連通凱萊圖是2-可擴的，同時討論了正則度在4以下的雙循環(huán)群凱菜圖的3-可擴性。第二節(jié)，我們介紹乘積圖可擴性的一些已知結(jié)論，最后一節(jié)中，我們證明了字典積可擴性的一個定理，即若G1是m-可擴圖，G2是n-可擴圖，則它們的字典積G2·G1是2（m+1）（n+1）-因子臨界圖。特別的，它也是（m+