Ramsey numbers of the quadrilateral versus books

被引:2
作者
Li, Tianyu [1 ]
Lin, Qizhong [1 ,3 ]
Peng, Xing [2 ]
机构
[1] Fuzhou Univ, Ctr Discrete Math, Dept Math, Fuzhou, Peoples R China
[2] Anhui Univ, Ctr Pure Math, Sch Math Sci, Dept Math, Hefei, Peoples R China
[3] Fuzhou Univ, Ctr Discrete Math, Dept Math, Fuzhou 350108, Peoples R China
基金
中国国家自然科学基金;
关键词
book; four-cycle; Ramsey number; GRAPHS; CYCLE;
D O I
10.1002/jgt.22919
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A book B-n is a graph which consists of n triangles sharing a common edge. In this paper, we study Ramsey numbers of quadrilateral versus books. Previous results give the exact value of r (C-4, B-n) for 1 <= n <= 14. We aim to determine the exact value of r (C-4, B-n) for infinitely many n. To achieve this, we first prove that r (C-4, B-(m -1)(2) +(t-2)) <= m(2) + t 2 for m >= 4 and 0 <= t <= m - 1. This improves upon a result by Faudree, Rousseau, and Sheehan which states that r (C-4, B-n) <= g (g (n)), where g (n) = n + left floor root n - 1 right floor + 2. Combining the new upper bound and constructions of C4-free graphs, we are able to determine the exact value of r (C4, Bn) for infinitely many n. As a special case, we show r (C-4, B-q(2) -q-2) = q(2) + q - 1 for all prime powers q >= 4.
引用
收藏
页码:309 / 322
页数:14
相关论文
共 17 条
[1]   The difference between consecutive primes, II [J].
Baker, RC ;
Harman, G ;
Pintz, J .
PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 2001, 83 :532-562
[2]   ON GRAPHS THAT DO NOT CONTAIN A THOMSEN GRAPH [J].
BROWN, WG .
CANADIAN MATHEMATICAL BULLETIN, 1966, 9 (03) :281-&
[3]  
Burr S.A., 1989, ANN DISCRETE MATH, V41, P79
[4]   EXISTENCE OF SPECIFIED CYCLES IN COMPLEMENTARY GRAPHS [J].
CHARTRAND, G ;
SCHUSTER, S .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1971, 77 (06) :995-+
[5]  
Erds P., 1966, Studia Sci. Math. Hungar., V1, P215
[6]  
FAUDREE R., 1978, P 9 SE C COMB GRAPH, P289
[7]  
FAUDREE RJ, 1991, ARS COMBINATORIA, V31, P239
[8]  
Kovari T., 1954, Colloquium Math., V3, P50
[9]  
Kung-Kuen Tse, 2006, Journal of Combinatorial Mathematics and Combinatorial Computing, V58, P97
[10]   LARGE BOOK-CYCLE RAMSEY NUMBERS [J].
Lin, Qizhong ;
Peng, Xing .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (01) :532-545