Polarity graphs and Ramsey numbers for C4versus stars

Xuemei Zhang, Yaojun Chen, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

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 languageEnglish
Pages (from-to)655-660
Number of pages6
JournalDiscrete Mathematics
Volume340
Issue number4
DOIs
Publication statusPublished - 1 Apr 2017

Keywords

  • Finite field
  • Polarity graph
  • Quadrilateral
  • Ramsey number
  • Star

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Cite this