奇星对九阶轮的Ramsey数(英文)

THE RAMSEY NUMBERS FOR STARS OF ODD SMALL ORDER VERSUS A WHEEL OF ORDER NINE

给定两个图G_1和G_2,Ramsey数R(G_1,G_2)是指具有如下性质的最小正整数n:对任意的n阶图G,或者G包含G_1,或者G的补图包含G_2.令S_n表示n阶星,W_m表示m+1阶轮.当n≥6且n是偶数时,人们证明了R(S_n,W_8)=2n+2.本文证明了当n=5,7,9时, R(S_n,W_8)=2n+1.

For two given graphs G_1 and G_2,the Ramsey number R(G_1,G_2)is the smallest positive integer n such that for any graph G of order n,either G contains G_1 or the complement of G contains G_2.Let S_n denote a star of order n and W_m a wheel of order m+1.It has been proved that R(S_n,W_8)=2n+2 for n≥6 and n is even. In this paper we show that R(S_n,W_8)=2n+1 for n=5,7,9.