圖的因子和圈.pdf

1、如果圖G的一個(gè)子圖F是G的一個(gè)支撐子圖，則稱F是G的一個(gè)因子。Akiyama和Kano將圖的因子問題分為兩類，分別稱為：度因子問題和分支因子問題。如果用因子的度來描述這個(gè)因子，則稱該因子為度因子。例如，如果一個(gè)因子F的所有度都等于1，F(xiàn)是一個(gè)1-因子。與此同時(shí)，哈密爾頓圈問題可以看成是尋找一個(gè)連通的因子使得每個(gè)點(diǎn)的度恰好等于2。另一個(gè)方面，如果一個(gè)因子是用圖的概念來描述，則成該因子為分支因子。例如，如果一個(gè)因子F的每個(gè)分支都是一條路，F(xiàn)

2、為路因子。如果F的每個(gè)分支要么是一個(gè)圈要么是一條邊，F(xiàn)也是一個(gè)分支因子，稱為完美2-匹配。 論文的第一個(gè)結(jié)果是對(duì)路因子覆蓋圖的刻畫。如果圖的每條邊都在某個(gè)路因子上，則稱這個(gè)圖是路因子覆蓋的。路因子覆蓋圖的重要性來源于它是對(duì)匹配覆蓋圖的推廣。Akiyama，Avis和Era證明了：圖G有一個(gè)路因子當(dāng)且僅當(dāng)對(duì)G的每個(gè)點(diǎn)子集S，G去掉S的孤立點(diǎn)的數(shù)目都小于等于S的2倍，對(duì)長路因子，Kaneko給出了Tutte-類型的刻畫：圖G有一個(gè)路

3、因子使得每條路都至少有3個(gè)點(diǎn)當(dāng)且僅當(dāng)對(duì)G的每個(gè)點(diǎn)子集S，G去掉S的太陽分支的數(shù)目都小于等于S的2倍?；谶@兩個(gè)結(jié)論，我們用收縮邊的方式給出了路因子覆蓋圖的充分必要條件。 論文的第二個(gè)部分研究了極小2-匹配覆蓋圖。如果圖G的每條邊都在G的一個(gè)完美2-匹配上，則稱圖G是一個(gè)2-匹配覆蓋圖。2-匹配覆蓋圖與可正則化圖是等價(jià)的?？烧齽t化圖的概念是由Berge提出并研究的。并且Berge給出了2-匹配覆蓋圖的Tutte-類型的刻畫。沿著這

4、個(gè)方向，我們定義了極小2-匹配覆蓋圖。一個(gè)2-匹配覆蓋圖G被稱為是極小的，如果G去掉任意一條邊都不是2-匹配覆蓋的。利用相同的技術(shù)，我們給出了2-匹配覆蓋圖的刻畫的新的證明。利用這個(gè)定理我們證明了：如果一個(gè)一個(gè)極小2-匹配覆蓋圖G不同構(gòu)于K2和K4，則G的最小度為2，并且G不含K2(n≥5)作為它的子圖，其它的性質(zhì)也相應(yīng)得到。 論文的最后部分致力于研究圖的圈方面的問題。我們證明了：對(duì)一個(gè)頂點(diǎn)數(shù)為n的9-連通圖，如果σ6(G)≥n

5、+4(α(G)-1)，則該圖是哈密爾頓的。我們還得到：如果一個(gè)n個(gè)頂點(diǎn)的(k+2)一連通滿足σk+3(G)≥n+k(k+2)，則該圖有一個(gè)k-控制圈,用相同的方法，對(duì)任意一個(gè)連通圖，論文給出了一個(gè)多項(xiàng)式時(shí)間算法要么輸出兩條不交的路要么輸出圖的一個(gè)結(jié)構(gòu)。 我們進(jìn)一步講研究方法推廣到對(duì)邊染色完全圖Kcn的研究。圖G的一個(gè)圈C稱為是交錯(cuò)的，如果C的相鄰兩條邊著有不同的顏色。Bollobas和Erdos在1976年猜想：如果△(Kcn)