Article ID Journal Published Year Pages File Type
5771585 Finite Fields and Their Applications 2017 13 Pages PDF
Abstract
For two given graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer N such that for any graph of order N, either G contains a copy of G1 or its complement contains a copy of G2. Let Cm be a cycle of length m and K1,n a star of order n+1. Parsons (1975) [6] shows that R(C4,K1,n)≤n+⌊n−1⌋+2 for all n≥2 and the equality holds if n is the square of a prime power. Let q be a prime power. In this paper, we first construct a graph Γq on q2−1 vertices without C4 by using the Galois field Fq, and then we prove that R(C4,K1,(q−1)2+t)=(q−1)2+q+t for q≥4 is even and t=1,0,−2, and R(C4,K1,q(q−1)−t)=q2−t for q≥5 is odd and t=2,4,...,2⌈q4⌉.
Related Topics
Physical Sciences and Engineering Mathematics Algebra and Number Theory
Authors
, , ,