Article ID Journal Published Year Pages File Type
4654117 European Journal of Combinatorics 2010 11 Pages PDF
Abstract

Given two graphs G1G1 and G2G2, denote by G1∗G2G1∗G2 the graph obtained from G1∪G2G1∪G2 by joining all the vertices of G1G1 to the vertices of G2G2. The Ramsey number R(G1,G2)R(G1,G2) is the smallest positive integer nn such that every graph GG of order nn contains a copy of G1G1 or its complement GcGc contains a copy of G2G2. It is shown that the Ramsey number of a book Bm=K2∗Kmc versus a cycle CnCn of order nn satisfies R(Bm,Cn)=2n−1R(Bm,Cn)=2n−1 for n>(6m+7)/4n>(6m+7)/4 which improves a result of Faudree et al., and the Ramsey number of a cycle CnCn versus a wheel Wm=K1∗CmWm=K1∗Cm satisfies R(Cn,Wm)=2n−1R(Cn,Wm)=2n−1 for even mm and n≥3m/2+1n≥3m/2+1 and R(Cn,Wm)=3n−2R(Cn,Wm)=3n−2 for odd m>1m>1 andn≥3m/2+1n≥3m/2+1 or n>max{m+1,70}n>max{m+1,70} or n≥max{m,83}n≥max{m,83} which improves a result of Surahmat et al. and also confirms their conjecture for large nn. As consequences, Ramsey numbers of other sparse graphs are also obtained.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,