摘  要: 对给定正整数n≥5，令 是n个顶点的轮， 是最大度为n-2的n个顶点的树，本文证明了

毕业论文关键词: 轮，树，Ramsey数58323

Abstract：For  given  positive  integer  , let  be the wheel with   vertices ,  and  let   be the unique tree with maximal degree  . In this paper, we prove that   and  , where   is  the  Ramsey number of   and  .

Keywords:  wheel,  tree,  Ramsey number

1.引言4

2.若干引理4

3.定理1的证明5

4.定理2的证明5

结论7

参考文献8

致谢9

1. 引言

本文中 是简单图，这里 为 的顶点集合， 为 的边集合。在图 中 表示 的边数， 为 的最大次数， 为顶点 的次数或度， 为 的补图。

树是无圈连通图。熟知， 个顶点的树恰有 条边。令 最大度为 个顶点的树, 是 个顶点的轮，其中一个顶点与其它顶点都相邻，称为轮 的中心，轮 中心之外顶点诱导子图为 个顶点的圈。

 Ramsey数  是最小自然数 ,使得对任何 阶图 ,或者 含有子图 ，或者 含有子图 .

本文主要证明如下结论：         本文中N表示正整数集合，[a]为不大于a的最大整数。 

2. 若干引理

通过阅读一些关于树与轮的书籍或期刊[1]-[7]，我们有如下一些引理：

引理1[7]:设 ，则                

 引理2[2]：设 ， ，则              

引理3[1]：设 为两个给定的图，若 且 则

 引理4[6]：设 , 则 .

3. 定理1的证明

   定理1： .   证明  由引理1及引理2知，

 ,   又由引理3知， ,

   由Ramsey数的定义知，若有6阶图 , 不含 , 不含 ,则 .

   构造下图 ,可以得出其补图 ：