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

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

上一篇:包含组合数的超同余式
下一篇:综合评价方法及其应用

基于决策树算法的篮球联赛预测

中美高中几何教学内容比...

中小学数学教材衔接研究...

中美初中数学教科书数与...

函数与不等式的关系研究

高中数学人教A版与北师大...

人教版华师大版中学数学...

老年2型糖尿病患者运动疗...

ASP.net+sqlserver企业设备管理系统设计与开发

安康汉江网讯

我国风险投资的发展现状问题及对策分析

网络语言“XX体”研究

张洁小说《无字》中的女性意识

麦秸秆还田和沼液灌溉对...

互联网教育”变革路径研究进展【7972字】

LiMn1-xFexPO4正极材料合成及充放电性能研究

新課改下小學语文洧效阅...