一致星因子圖與籠的連通性.pdf

1、1940年，Turan首先將極圖理論作為一個學科來研究，Paul Erdos進而推動了這一理論的發(fā)展。自此，極圖理論成為圖論的一個重要分支。在極圖理論里，我們所感興趣的是圖的各種不變量之間的關系，這些不變量包括頂點數、邊數、連通度、最小度、直徑等。此外，多大的這些不變量才能保證圖具有某些性質，這也是我們所感興趣的地方。通常對一類圖H，給定性質p和一個不變量μ，我們希望確定出最小的值m，使得H中每個滿足μ(G)>m的圖G都具有性質p。我們

2、稱H中的那些不具有性質p且μ(G)=m的圖G為此問題下的極圖。舉個例子，每個頂點數為n，邊數至少為n的圖一定包含圈，那么在這個問題下的極圖就是所有頂點數為n的樹。說到這里，我們需要強調下，本文中所說的極圖理論是指廣義的，它可以包括各種結構性結果。
　　 在本文中，我們主要討論了兩類極圖。一類是關于一致星因子圖的刻畫，另一類則是關于籠的連通性。在第一章中，我們將會介紹一些基本的定義和相關問題的歷史背景。
　　 我們稱同構于

3、K1，n的樹為星，這里n≥1。如果圖G的某個生成子圖的所有分支都是星，則稱這個生成子圖足圖G的一個星因子。圖G的邊賦權函數是指ω：E(G)→N+，這里N+表示正整數集合。設H是圖G的一個子圖，在G的邊賦權函數ω下，圖H上所有邊的權和稱為H的權，也就是說，ω(H)=∑e∈E(H)ω(e)。如果圖G存在一個邊賦權函數ω，使得G的每個星因子的權都相等，那么我們則稱圖G是一致星因子圖。一致星因子圖的概念是由Hartnell和Rall在文[24]

4、中提出的。在第二章里，我們首先用Gallai－Edmonds匹配結構定理給出在常函數邊賦權條件下，所有一致星因子圖的完整刻畫；然后給出在一般邊賦權函數條件下，所有圍長至少為5的一致星因子圖的一個清晰刻畫。
　　 如果一個k-正則圖G的圍長為g，則稱它為(k，g)-圖。對給定的k和g，含有最少頂點數的(k，g)-圖則稱之為籠?；\問題是圖論中最古老的問題之一?；\是由Tutte[52]在1947提出的，此后得到廣泛地研究，然而這個課題