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

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

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

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

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