双星图的Ramsey数的上界

An Upper Bound for the Ramsey Numbers of Bistars

摘要:

对给定的两个图G和H, Ramsey数R(G,H)是最小的正整数N，使得对完全图KN的边任意红/蓝着色，则或者存在红色子图G，或者存在蓝色子图H.双星B(m,n)为直径是3,有两个中心顶点, 其顶点度分别为m+1和n+1的树.得到，当n>m时,R(B(m,n))<2n+m+2；当n=m或n=m+1时, R(B(m,n))=2m+n+2.

Abstract:

For two given graphs G and H, Ramsey number R(G,H) is the smallest integer N such that any red/blue edgecoloring of KN contains a red copy of G or a blue copy of H. Let a bistar B(m,n) be a tree of diameter three with two central vertices of degree m+1 and n+1, respectively. It is shown that R(B(m,n))<2n+m+2 for n>m; and R(B(m,n))=2m+n+2 for n=m or n=m+1. Key words： Ramsey number; tree; bistar