书图和扇形图的Ramsey数

Ramsey Numbers of Books and Fans

摘要:

对给定的两个图G和H，Ramsey数R(G,H)是最小的正整数N，使得对完全图KN的边任意红/蓝着色，或者存在红色子图G，或者存在蓝色子图H.用G+H表示两个不交的图G和H之间完全连边所得到的图.设Bm=K2+mK1，Fn=K1+nK2.证明了当m≥1且n≥max{2,3m-2},R(Bm,Fn)=4n+1；当n≥38,R(F2,K2,n)=2n+3.

Abstract:

For given graphs G and H, Ramsey number R(G,H) is the smallest positive integer N such that any red/blue edgecoloring of KN contains either a red copy of G or a blue copy of H. Denote by G+H the graph obtained from disjoint G and H by adding edges connecting G and H completely. Let Bm=K2+mK1 and Fn=K1+nK2. It is shown that R(Bm,Fn)=4n+1 for n≥max{2,3m-2}； and R(F2,K2,n)=2n+3 for n≥38.