Ramsey Numbers of C 4 versus Wheels and Stars
Ramsey Numbers of C 4 versus Wheels and Stars
复制标题
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Yali Wu;Rui Zhang;P. Stanislaw;Radziszowski
中科院分区：
文献类型：
--
作者：
Yali Wu;Rui Zhang;P. Stanislaw;Radziszowski
Let ex ( n , C 4 ) denote the maximum size of a C 4 -free graph of order n . For an even integer or odd prime power q , we prove that ex ( q 2 + q + 2 , C 4 ) < 12 ( q + 1 )( q 2 + q + 2 ) , which leads to an improvement of the upper bound on Ramsey numbers R ( C 4 , W q 2 + 2 ) , where W n is a wheel of order n . By using a simple polarity graph G q for a prime power q , we construct the graphs whose complements do not contain K 1 , m or W m , and then determine some exact values of R ( C 4 , K 1 , m ) and R ( C 4 , W m ) . In particular, we prove that R ( C 4 , K 1 , q 2 − 2 ) = q 2 + q − 1 for q ≥ 3, R ( C 4 , W q 2 − 1 ) = q 2 + q − 1 for q ≥ 5, and R ( C 4 , W q 2 + 2 ) = q 2 + q + 2 for q ≥ 7.
