關(guān)于圖的[k，k+1]-因子的若干結(jié)果.pdf

1、隨著大型計算機(jī)的出現(xiàn)和計算機(jī)科學(xué)的迅速發(fā)展，特別值得一提的是計算機(jī)網(wǎng)絡(luò)的出現(xiàn)和發(fā)展，大大地促進(jìn)了圖論的發(fā)展和繁榮，無論在數(shù)學(xué)，物理，化學(xué)，生物等基礎(chǔ)學(xué)科，還是在交通運(yùn)輸，計算機(jī)科學(xué)，系統(tǒng)工程等應(yīng)用領(lǐng)域，圖論都顯示出越來越重要的作用，因而研究圖論問題及其解法具有重要的理論和實際意義。 本文主要研究了二分圖的哈密頓[k，k+1]-因子與其頂點度之間的關(guān)系。第一章對研究的背景和現(xiàn)狀進(jìn)行了概述；第二章介紹了與研究有關(guān)的一些術(shù)語及記號；第

2、三章重點研究二分圖中包含任意給定的哈密頓圈的[k，k+1]-因子的度條件。 自從1952年以來，對圖的因子理論的研究進(jìn)展十分迅速，到現(xiàn)在已有很多的研究成果。圖的因子理論與很多圖論中的其它知識有關(guān)，如圖的因子與堅韌度之間有聯(lián)系。1971年，Chvatal提出了下面的猜想：若圖G是3/2-堅韌的，則G有2-因子。該猜想至今未得到證實。圖的因子與其頂點度數(shù)之間也有緊密地聯(lián)系，1992年，T.Nishimura提出了下面的猜想：設(shè)G是一

3、個n階圖，對任意x，y∈V(G)，如果x與y之間的距離dG(x，y)=2，且max{dG(x)，dG(y)}≥n/2，n≥4k-3，kn為偶數(shù)，則圖G有k-因子。該猜想也沒有完全解決，1997年錢建波證明了該猜想對二分圖成立，同年T.Niniessen證明了當(dāng)n≥8k2+12k+6時該猜想成立。1998年蔡茂誠給出了：設(shè)G是一個n階圖，對不相鄰的兩個頂點x，y∈V(G)，如果dG(x)+dG(y)≥n，則圖G中包含任意給定的哈密頓圈C的

4、[k，k+1]-因子。2002年，H.Matsuda[14]改進(jìn)為：設(shè)k為正整數(shù)，且k≥2，G是階|G|≥3的2-連通圖，δ(G)≥k，對偶數(shù)|G|有|G|≥8k-16且對奇數(shù)|G|有|G|≥6k-13，如果G中每一對不相鄰的頂點x和y有max{dG(x),dG(y)}≥|G|/2則對G的任意哈密頓圈C，G有[k，k+1]-因子包含圈C。 本文給出了二分圖中包含任意給定的哈密頓圈C的[k，k+1]-因子的度條件，即：1.設(shè)G是頂

5、點數(shù)為n的均衡二分圖，且是n/4+1臨界圖，n≥8k-12，n≥12，k≥2，則對G的任意哈密頓圈C，G有[k，k+1]-因子包含圈C。 2.設(shè)k≥2，G=(X，Y，E)中，|X|=|Y|=n/2≥4(k-2)-1，n≥6，δ(G)≥k，k為正整數(shù)。如果G的每一對距離為2的頂點u，v有max{dG(u)，dG(v)}≥n/4+2，則對G的任意哈密頓圈C，G有[k，k+1]-因子包含圈C。 3.設(shè)G=(X，Y，E)，|X|

6、=|Y|=n/2≥4(k-2)-3，k≥2且n≥6，δ(G)≥k，若G中每一對不相鄰的頂點u，v有max{dG(x)，dG(x)}≥n/4+2，則G有包含哈密頓圈C的[k，k+1]-因子。 4.設(shè)二分圖G=(X，Y，E)，|X|=|Y|=n/2≥4(k-2)-3，k≥2且n≥6，δ(G)≥k，若G中每一對不相鄰的頂點u，v有dG(u)+dG(v)≥n/2+4，則G有包含哈密頓圈C的[k，k+1]-因子。 此度條件改進(jìn)了階