摘要：设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。得证。