Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648921 | Discrete Mathematics | 2007 | 7 Pages |
Abstract
For two given graphs G1G1 and G2G2, the Ramsey number R(G1,G2)R(G1,G2) is the smallest integer nn such that for any graph GG of order nn, either GG contains G1G1 or the complement of GG contains G2G2. Let CmCm denote a cycle of length m and KnKn a complete graph of order nn. It was conjectured that R(Cm,Kn)=(m-1)(n-1)+1R(Cm,Kn)=(m-1)(n-1)+1 for m⩾n⩾3m⩾n⩾3 and (m,n)≠(3,3)(m,n)≠(3,3). We show that R(C6,K7)=31R(C6,K7)=31 and R(C7,K7)=37R(C7,K7)=37, and the latter result confirms the conjecture in the case when m=n=7m=n=7.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
T.C. Edwin Cheng, Yaojun Chen, Yunqing Zhang, C.T. Ng,