Abstract
For two given graphs G1and 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 G1or its complement contains a copy of G2. Let Cmbe a cycle of length m and K1,na star of order n+1. Parsons (1975) shows that R(C4,K1,n)≤n+⌊n−1⌋+2 and if n is the square of a prime power, then the equality holds. In this paper, by discussing the properties of polarity graphs whose vertices are points in the projective planes over Galois fields, we prove that R(C4,K1,q2−t)=q2+q−(t−1) if q is an odd prime power, 1≤t≤2⌈q4⌉ and t≠2⌈q4⌉−1, which extends a result on R(C4,K1,q2−t) obtained by Parsons (1976).
Original language | English |
---|---|
Pages (from-to) | 655-660 |
Number of pages | 6 |
Journal | Discrete Mathematics |
Volume | 340 |
Issue number | 4 |
DOIs | |
Publication status | Published - 1 Apr 2017 |
Keywords
- Finite field
- Polarity graph
- Quadrilateral
- Ramsey number
- Star
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics