论文部分内容阅读
图论是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学,尤其是计算机科学中有非常广泛的应用.
本文主要研究某些图的Ramsey数问题.对任意两个图G和H,图的Ramsey数R(G,H)定义为最小的整数n,使得阶数为n的任意图F都包含G作为子图或(F)包含H作为一个子图.本文研究了树对轮的Ramsey数.本文主要内容及结构如下:
在第一章中简要叙述了图Ramsey数的发展,介绍了图论的基本概念和术语.
由于星图的特殊性,星图对其它图的Ramsey数得到了广泛的关注.在第二章中研究的是星对轮的Ramsey数.在本章中先给出并证明了关于图的Ramsey数的一些结果.然后利用文献[26]和[32]介绍并讨论了星对轮的一些结果.
路径也是一类特殊的图.许多数学工作者都对关于路径或轮的Ramsey数进行了研究.在第三章我们研究的是路径对轮的Ramsey数.Faudree等人考虑了所有路径对圈的Ramsey数.Surahmatetal得到了路径对W4或W5的Ramsey数.陈耀军从更一般的情况考虑了路径对轮的Ramsey数并给出了下面的结果:R(Pn,Wm)=3n-2,对奇数m且n≥m-1≥2;R(Pn,Wm)=2n-1,对偶数m且n≥m-1≥3.因此在第二节中我们就给出了路径对轮在其他情况下的结果:
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-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,其中n≥4;R(Tn,W5)=3n-2,其中n≥5.所以E.T.Baskoro猜想了下面的结果当n≥m≥7且m为奇数时,R(Tn,Wm)=3n-2.本章第二节中我们就证明了当m为奇数且m≥7时,R(Tn,Wm)=3n-2,其中n=m,m+1,m+2.