關于一些圖的Ramsey數.pdf

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

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

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

4、1時2n-1當n≥4且偶數m有4≤m≤n+1時以及這樣一個邊界：若(n≥6，m為偶數且n+2≤m≤2n-4)或(n為偶數，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數.E.T.Baskoro給出了樹對W4或W5的Ramsey數：R(Tn，W4)=2n-1，其