Some values of Ramsey numbers for C-4 versus stars
Some values of Ramsey numbers for C-4 versus stars
复制标题
C4 与恒星的拉姆齐数的一些值
DOI：
10.1016/j.ffa.2016.11.012
复制
发表时间：
2017
影响因子：
1
通讯作者：
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）[6]证明了对于所有n≥ 2，R（C4，K1，n）≤ n+<$n− 1 <$+ 2，并且当n是素数幂的平方时等式成立。设q为素数幂。本文首先利用Galois域Fq构造了一个不含C4的q2 - 1个顶点的图Γ q，然后证明了R（C 4，K 1，（q− 1）2+ t）=（q− 1）2+ q+ t，其中q≥ 4为偶数，t= 1，0，− 2，R（C 4，K 1，q（q− 1）− t）= q 2− t，其中q≥ 5为奇数，t= 2，4，.，2004年4月。
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)[6] shows that R (C 4, K 1, 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 Γ q on q 2− 1 vertices without C 4 by using the Galois field F q, and then we prove that R (C 4, K 1,(q− 1) 2+ t)=(q− 1) 2+ q+ t for q≥ 4 is even and t= 1, 0,− 2, and R (C 4, K 1, q (q− 1)− t)= q 2− t for q≥ 5 is odd and t= 2, 4,..., 2⌈ q 4⌉.