Polarity graphs and Ramsey numbers for versus stars

详细信息    查看全文

• 作者：Xuemei Zhang^a ; ^b ; Yaojun Chen^a ; ^{yaojunc@nju.edu.cn} ; T.C. Edwin Cheng^c
• 关键词：Finite field ; Polarity graph ; Ramsey number ; Star ; Quadrilateral
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：340
• 期：4
• 页码：655-660
• 全文大小：414 K
• 卷排序：340

文摘

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 of order NN, either GG contains a copy of G1G1 or its complement contains a copy of G2G2. Let CmCm be a cycle of length mm and K1,nK1,n a star of order n+1n+1. Parsons (1975) shows that R(C4,K1,n)≤n+⌊n−1⌋+2 and if nn 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)R(C4,K1,q2−t)=q2+q−(t−1) if qq is an odd prime power, 1≤t≤2⌈q4⌉ and t≠2⌈q4⌉−1, which extends a result on R(C4,K1,q2−t)R(C4,K1,q2−t) obtained by Parsons (1976).