一些特殊图的Ramsey数

摘要：设T*(V,E*)，T'(V,E')是n个顶点的两棵树，其中V{v,v,,v }，

n n 0 1 n1

E{v0v1,v0v2,,v0vn3,vn3vn2,vn2vn1}，E{v0v1,v0v2,,v0vn2,vn2vn1}，本文运用孙智

宏老师给出的一些引理求出Ramsey数72628

r(T*,T*)，

r(T',T*)和

r(T',T*)的精

确值。

7 7 6 6

关键词：树，Ramsey数，Turan型问题

Abstract: Let

T*(V,E*)

and

T'(V,E')

be two trees on n vertices,

where

V{v0,v1,

vn1}

，E*

{v0v1,v0v2,v0vn3,vn3vn2,vn2vn1}

and

E{v0v1,v0v2,,v0vn2,vn2vn1}。Inthispaper,byusingsomelemmasduetoZhi-HongSun

wedeterminetheRamseynumbersfor

r(T*,T*),

r(T',T*)and

r(T',T*)。

7 7 6 6 7 7 6 6

Keywords：tree,Ramseynumber,Turan’sproblem

1 引言 4

2 主要结果及其证明 5

结论 21

参考文献 22

1 引言

设G=V(G),E(G)为图,其中VG表示G的顶点集合,EG表示G的边集合。G是G的补图。树是无圈的连通图。熟知n个顶点的的树Tn恰有n1条边。图的Turan型问题欲求不含给定图L为子图的p阶图最多边数ex(p;L)。Ramsey数r(G1,G2)是最小自然数p使得

对任何p阶图G，或者G含有子图G，或者G含有子图G。

1 2

设T*(V,E*)与T'(V,E')为n个顶点的两棵树,其中V{v,v,,v }，

n n 0 1 n1

E{v0v1,v0v2,,v0vn3,vn3vn2,vn2vn1}，E{v0v1,v0v2,,v0vn2,vn2vn1}，如下图：

v0 v0

vn2

vn3

vn1

vn2

n n vn1

本文中表示正整数集合，x表示不超过x的最大整数，G为图G的补图，dv表

示v的次数，G、G分别为G的最大度与最小度，Km,n为完全二部图。孙智宏老师在论文[1-2]中给出以下引理：一些特殊图的Ramsey数:http://www.youerw.com/shuxue/lunwen_82655.html