關(guān)于一些圖的Ramsey數(shù).pdf

1、圖論是離散數(shù)學(xué)的一個(gè)重要分支，它在物理、化學(xué)、天文、地理、生物學(xué)，尤其是計(jì)算機(jī)科學(xué)中有非常廣泛的應(yīng)用. 本文主要研究某些圖的Ramsey數(shù)問題.對任意兩個(gè)圖G和H，圖的Ramsey數(shù)R(G，H)定義為最小的整數(shù)n，使得階數(shù)為n的任意圖F都包含G作為子圖或(F)包含H作為一個(gè)子圖.本文研究了樹對輪的Ramsey數(shù).本文主要內(nèi)容及結(jié)構(gòu)如下： 在第一章中簡要敘述了圖Ramsey數(shù)的發(fā)展，介紹了圖論的基本概念和術(shù)語. 由

2、于星圖的特殊性，星圖對其它圖的Ramsey數(shù)得到了廣泛的關(guān)注.在第二章中研究的是星對輪的Ramsey數(shù).在本章中先給出并證明了關(guān)于圖的Ramsey數(shù)的一些結(jié)果.然后利用文獻(xiàn)[26]和[32]介紹并討論了星對輪的一些結(jié)果. 路徑也是一類特殊的圖.許多數(shù)學(xué)工作者都對關(guān)于路徑或輪的Ramsey數(shù)進(jìn)行了研究.在第三章我們研究的是路徑對輪的Ramsey數(shù).Faudree等人考慮了所有路徑對圈的Ramsey數(shù).Surahmatetal得到了

3、路徑對W4或W5的Ramsey數(shù).陳耀軍從更一般的情況考慮了路徑對輪的Ramsey數(shù)并給出了下面的結(jié)果：R(Pn，Wm)=3n-2，對奇數(shù)m且n≥m-1≥2；R(Pn，Wm)=2n-1，對偶數(shù)m且n≥m-1≥3.因此在第二節(jié)中我們就給出了路徑對輪在其他情況下的結(jié)果： R(R，Wm)={1當(dāng)n=1且m≥3時(shí)m+1當(dāng)n=2且m≥3或n=3且偶數(shù)m≥4時(shí)m+2當(dāng)n=3且奇數(shù)m≥5時(shí)3n-2當(dāng)m=n=3或n≥4,m為奇數(shù)且1≤m≤2n-

4、1時(shí)2n-1當(dāng)n≥4且偶數(shù)m有4≤m≤n+1時(shí)以及這樣一個(gè)邊界：若(n≥6，m為偶數(shù)且n+2≤m≤2n-4)或(n為偶數(shù)，n≥4，m=2n-2或m≥2n)，則m+[3n/2]-2≥R(Pn，Wm)≥max{[m-1/n-1](n-1)+n，m+[m-1/[m-1/n-1]]}.星和路徑都是特殊的樹，因此在第四章章中我們來研究樹對輪的Ramsey數(shù).E.T.Baskoro給出了樹對W4或W5的Ramsey數(shù)：R(Tn，W4)=2n-1，其