毕业论文

打赏
当前位置: 毕业论文 > 数学论文 >

轮与树的Ramsey数

时间:2020-10-20 20:21来源:毕业论文
对给定正整数n≥5,令 是n个顶点的轮, 是最大度为n-2的n个顶点的树,本文证明了

摘  要: 对给定正整数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阶图 , 不含 , 不含 ,则 .

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

轮与树的Ramsey数:http://www.youerw.com/shuxue/lunwen_63225.html
------分隔线----------------------------
推荐内容