摘要:设r(G;H)为两个图G与H的Ramsey数,本文中我们对G、H为含有两个三角形的扇,较大度的n阶树及偶数个顶点的轮,确定了一些Ramsey数的精确值。

毕业论文关键词:Ramsey数,扇,轮,树91145

Abstract: Let r(G;H) be the Ramsey numbers of graphs G and H。 In this paper, we give explicit formulas for r(G;H) when G and H are among the fan with two triangles, the tree of order n with large degree and the wheels with even vertices。

Keywords: Ramsey number, fan, wheel, tree

目录

1引言 4

2基本引理 6

3主要结果 8

结论 11

参考文献 12

1引言

Ramsey数理论是组合数学和图论的重要分支,Ramsey数的确定比较困难,但具有理论价值及实践意义。本文通过构造合适的图,确定一些特殊图Ramsey数的下界,通过利用已有的Turan型问题结论获得Ramsey数的较好上界,最终得到一些特殊图的Ramsey数精确值。

本文所用的图都是简单图。我们用GVG,EG表示图,其中VG表示顶点集合,EG表示边集合。扇F2是有一个公共顶点的两个三角形所构成的5阶图,扇F2如下所示:

Cn表示长度为n的圈,轮Wn是由一个顶点与Cn1的所有顶点相连构成的。其中,轮W5如下图所示:

K表示顶点二分类中分别有m个和n个顶点的完全二部图。Tn,3表示将n个顶点尽可能平均分为三类而任两分类中顶点都相邻的Turan图。rG1;G2是最小的正整数p使得对任何p阶图G,或者G含有子图G1,或者G的补图G含有子图G2。exp;H表示不含指定图H为子图的p阶图的最多边数。本文给出了rF2;H2n1的H满足的条件,由此确定了一些特殊图Ramsey数,特别得到了轮W5及偶数轮与度较大的n阶树的Ramsey数。本文利用一些特殊图H的exp;H公式求rF2;H的上界,这里图H包含Pn,Tn,Tn,Tn,Tn,文献综述

其中Pn是有n个顶点的路。Tn,Tn,Tn,Tn分别如下图所示:本文中N表示正整数集合,[x]表示不超过x的最大整数。

2基本引理

对于Ramsey数上界的确定,有如下有用的引理:

引理2。13G1和G2是两个图,若

pN,pmaxVG,VG且

则rG1;G2p。

exp;G1exp;G2⎜ ⎟,

⎝2⎠证明设G是p阶图。若eGexp;G1

且eGexp;G

exp;G1exp;G2eGeG⎜ ⎟。

⎝2⎠这与假设矛盾,所以eGexp;G1

或eGexp;G

。因此G包含G1为子图或

者G包含G2为子图,即rG1,G2VGp。得证。

上一篇:AHP淮安市滑坡影响因子评价指标体系建立
下一篇:没有了

图的伴随多项式的根的刻画及应用

函数图象的对称性研究

几类特殊不等式的证明与推广形式及应用

多媒体背景下小学生空间...

基于DEM三维数字地图导航方法研究

Ferrers图在分拆计数中的应用

CT图像滤波反投影重建算法的研究

幼儿园中班幼儿生活卫生习惯培养

试析山岭隧道岩溶地质处理【2342字】

基于供应链的合作营销策略研究

matlab基于视频虚拟线圈的车流统计技术研究

企业并购会计问题研究+文献综述

優质护理茬颈椎病患者围...

轨道交通隧道内无线电波...

小學一年级英语启蒙教學...

柔性关节建模与控制方法研究Matlab仿真

企业生命周期视角的阿里企业文化分析