Polarity graphs and Ramsey numbers for C-4 versus stars
Polarity graphs and Ramsey numbers for C-4 versus stars
复制标题
C-4 与恒星的极性图和拉姆齐数
DOI：
10.1016/j.disc.2016.12.005
复制
发表时间：
2017
影响因子：
0.8
通讯作者：
Cheng T. C. Edwin
中科院分区：
文献类型：
--
作者：
Zhang Xuemei;Chen Yaojun;Cheng T. C. Edwin
对于给定的两个图G1和G2，Ramsey数R(G1，G2)是最小整数N，使得对于任何N阶图，G包含G1的副本或其补包含G2的副本.设Cm是长度为m的圈，K1，n是n+1阶星.Parsons(1975)证明了R(C4，K1，n)≤n+⌊n−1⌋+2，如果n是素数幂的平方，则等式成立.通过讨论点为Galois域上射影平面上的点的极图的性质，证明了当q为奇素数幂时，R(C4，K1，q2−t)=q2+q−(t−1)，1≤t≤2⌈q4⌉和t≠2⌈q4⌉−1，推广了Parsons(1976)关于R(C4，K1，q2−t)的一个结果.
For two given graphs G 1 and G 2, the Ramsey number R (G 1, G 2) is the smallest integer N such that for any graph of order N, either G contains a copy of G 1 or its complement contains a copy of G 2. Let C m be a cycle of length m and K 1, n a star of order n+ 1. Parsons (1975) shows that R (C 4, K 1, 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 (C 4, K 1, q 2− t)= q 2+ q−(t− 1) if q is an odd prime power, 1≤ t≤ 2⌈ q 4⌉ and t≠ 2⌈ q 4⌉− 1, which extends a result on R (C 4, K 1, q 2− t) obtained by Parsons (1976).