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

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

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

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

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