不含偶圈c_2c2m_的r色ramsey数r_2cr_(c_2c2m_)的下界

《不含偶圈c_2c2m_的r色ramsey数r_2cr_(c_2c2m_)的下界》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、不古偶圈c2。的，色Ramsey数q(c2，)的下界当禁止子图H为奇圈C2¨时，2’晰p一1)(Ⅲ一1)。通过参考R3(c3)=17Ⅲ，R3(c4)=11[5116]，R3(G)=17[7]’R3(c6)=12[81，R3(c7)=25‘9l以及猜想R3(C2卅十1)=8m十1(m≥2)㈣等相关文献，本文对H兰C2。情况下的尺，(日)的下界进行了较为详细的讨论，给出并证明了Ramsey数R，(c：。)一个更好的下界；并结合构造性证明的方

2、法得到尺，(G)的精确值，进一步给出关于R，(c：。)(卅≥3)的一个猜想。不含偶圈c孙的r色Ramsey数R，(c2。)的下界1相关概念Rmnsey理论是组合数学的重要分支，Ramsey问题也是图论中的一个重要研究课题。它表明：每一种“不规则”的结构，只要它足够大，就会含有指定大小的“规则”子结构f21。本文所研究的“不含偶圈C2。的r色Ramsey数R，(c2。)的下界”是图论领域Ramsey问题的一个重要的课题。为了在叙述中避免歧义，有必要先说明一下在本文中涉及到的图论概念。1．1本文涉及的图论概念1．1．1图

3、的基本概念现实世界的许多事物或现象之间存在着某种联系，为了从这些联系中找出规律，人们经常使用点表示要研究的事物或对象，用点与点之间的连线表示彼此间内在的联系，这类事例的数学抽象就产生了图的概念。例如，在通讯网络的研究中，我们经常使用点表示通讯站，而用连线表示通讯线路。夺图一个图G定义为一个二元组(矿(G)，E(G))，简记作G=(V，E)。其中V(G)={v。，v：，⋯，v。)表示一个非空的顶点集合；E(G)表示连接顶点的边集，其中每一条边与其两个端点相关联(Incident)。若E(G)中的边与顶点的无序对(v。，

4、v，)相关联，则称该边为无向边；若E(G)中的边与顶点的有序对相关联，则称该边为有向边。每一条边都是无向边的图称为无向图：每一条边都是有向边的图称为有向图：既有无向边，又有有向边的图称为混合图。在一个图中，若两个顶点由一条边相关联，则这两个顶点称为邻接点；与顶点v(v∈V)相邻接的点的集合记作Ⅳ(v)，N(v)={U：v“∈E(G)}；用N[v】表示N[v】-{v)UN(v)，称作顶点v的闭邻接点集；不与任何顶点相邻接的顶点称为孤立点；仅由孤立点组成的图称为零图；仅由一个孤立点组成的图称为平凡图。类似于

5、邻接点的概念，关联于同一个顶点的两条边称为邻接边：关联于同一个顶点的一条边称为自回路或环(Loop)。环的方向是没有意义的，它既可作为有向边，也可作为无向边。关联于同～对顶点的两条或两条以上的边称为平行边；含有平行边的任何一个图称不含偶圈C2。的，色Ramsey数B(c2。)的下界为多重图：不含有平行边和环的图称为简单[](SimpleGraph)。顶点集和边集都有限的图称为有限图。本文所涉及的图均为有限的简单无向图。图G=(y，E)中，任意一条边(“，v)可简记“v；G顶点的个数称为阶(Order)，用p(G)=l

6、V(G)l来表示；G的边数(Size)，用q(G)=IE(G)I来表示。由图的定义可知，一个集合V和矿上的一个二元关系就是一个图。因此图的最本质的内容就是一个二元关系，也就是顶点和边的关联关系。一个系统或一个结构若具有二元关系便可用图作为数学模型。夺度在图G=(V，E)中，与顶点v(v∈V)关联的边数，称作是该顶点的度(Degree)，汜作d(v)；其中顶点度最大的值称为图G的最大度，记作△(G)=ma)({d(v)：v∈n：顶点度最小的值称为图G的最小度，记作6(G)=min{d(v)：v∈y)。在有向图中，射入一

7、个顶点的边数称为该顶点的入度；由一个顶点射出的边数称为该顶点的出度。顶点的出度与入度之和就是该顶点的度数。在任何有向图中，所有顶点的入度之和等于所有顶点的出度之和。每个图中，顶点度数的总和等于边数的两倍，即∑d(V)=21E(G)I。vEr(G)夺完全图简单图G=(V，E)中，若每一对顶点间都有边相连，则称该图为完全图；有n个顶点的完全图记作世。，其边数为n(n一1)／2。夺二部图如果一个图的顶点集能被分成两个不相交的集合K，以(称为部分集)，且每条边将K中的顶点与K中的顶点相连，则称此图为二部图，有时也称为二分图或

8、偶图。若K中的每个顶点与％中的每个顶点都相邻，则称此二部图为完全二部图，记为K⋯．，其中P．=吲，P：=I％I。完全m(m>1)部图，该图共有P．+P：+⋯+p，个顶点，这些顶点被分到m个集合中，各个集合分别包含P，，P：，⋯，P。(只>0)个顶点，属于同一个集合中的顶点均不连结，属于不同集合中的顶点均相互联结。完全m部图可表示为：世⋯，．。。