余　培， 陈　明， 李雨生

(同济大学 数学系，上海 200092)



一些扫帚图的Ramsey数

余培， 陈明， 李雨生

(同济大学 数学系，上海 200092)

摘要：给定图G，Ramsey数R(G)是最小的正整数N，满足对完全图 KN的边任意红蓝着色，则或者存在红色子图G或者存在蓝色子图G.扫帚图Bk，m是将星图K1,k的中心点与路Pm的一个端点黏成一个点得到的树图.由此得到,当k为大于1的正整数时，R(Bk,2k-1)=4k-2且R(Bk,4)=2k+3.

关键词：Ramsey数； 树； 扫帚图

1研究背景

本文研究的图均为简单图.任给图G和H，Ramsey数R(G,H)是最小的正整数N，满足对完全图KN的边任意红蓝着色，则或者存在红色子图G或者存在蓝色子图H.当G=H时，简记R(G,G)为R(G).

Ramsey数一直都是国际上比较热门的研究课题之一.以Tn表示具有n个点的树.作为最简单的图类，R(Tn)的研究备受关注.其中两类经典的图类是星图和路. 记K1,n-1是星图，也即一个点下面挂了n-1条边；Pn是有n个点的路.它们的Ramsey数如下,分别见文献[1-3].

-1.

本文的研究对象是扫帚图Bk,m.扫帚图Bk，m是将星图K1,k的中心点与路Pm的一个端点黏成一个点后所得到的树图.由定义可知：B1,m是路Pm+1；Bk,1=K1,k,Bk,2=K1,k+1是星图.Erdös,Faudree等人在文献[4]中得到：R(Tn)的最小下界能在某些Bk,m中达到，同时猜测R(Tn)的最大上界也能在某些Bk,m中达到，故研究R(Bk,m)是非常有意义的.

目前扫帚图研究的主要结果是Erdös,Faudree等人在文献[4]中得到的，如下：

(2) 当5≤m≤2k-1时，R(Bk,m)≤2k+m.

当m=1,2时，Bk,1，Bk,2是星图，由引理2可得到R(Bk,1),R(Bk,2)的值；当m=3时，Bk,3是双星图，Guo和Volkman在文献[5]得到R(Bk,3)的值.因此还未确定的是当m=4，以及当5≤m≤2k-1时的情况.本文得到如下结果.

定理1设k是正整数，则R(Bk,2k-1)=4k-2.

定理2设k≥2为正整数，则R(Bk,4)=2k+3.

2主要结果的证明

已知图G，以V(G)表示图G的顶点集.当给图G的边红蓝染色后，记其中红色子图为R，蓝色子图为B.已知v是图G中的任意点，记N(v)={u|点u，v之间连边}为点v的邻域；……