一些扫帚图的Ramsey数

Ramsey Number for Some Brooms

摘要:

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

Abstract:

For a given graph G, Ramsey number R(G) is the smallest integer N such that any red/blue edgecoloring of KN contains a red copy or a blue copy of G. Let broom Bk,m be a tree obtained by identifying the central vertex of a star K1,k with an endvertex of Pm. It is proven that R(Bk,2k-1)=4k-2 and R(Bk,4)=2k+3 for integer k>1.