Some values of Ramsey numbers for C4versus stars

Xuemei Zhang, Yaojun Chen, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 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) [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 Γqon q2−1 vertices without C4by 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⌉.
Original languageEnglish
Pages (from-to)73-85
Number of pages13
JournalFinite Fields and Their Applications
Volume45
DOIs
Publication statusPublished - 1 May 2017

Keywords

  • Finite fields
  • Quadrilateral
  • Ramsey graph
  • Ramsey number
  • Star

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Engineering(all)
  • Applied Mathematics

Cite this