Ramsey numbers of long cycles versus books or wheels
Given two graphs \(G_{1}\) and \(G_{2}\), denote by \(G_{1}*G_{2}\) the graph obtained from \(G_{1}\cup G_{2}\) by joining all the vertices of \(G_{1}\) to the vertices of \(G_{2}\). The Ramsey number \(R(G_{1},G_{2})\) is the smallest positive integer n such that every graph \(G\) of order \(n\) contains a copy of \(G_{1}\) or its complement \(G^{c}\) contains a copy of \(G_{2}\). It is shown that the Ramsey number of a book \(B_{m}=K_{2}*K_{m}^{C}\) versus a cycle \(C_{n}\) of order \(n\) satisfies \(R(B_{m},C_{n})=2n-1\) for \(n>(6m+7)/4\) which improves a result of Faudree et al. [\textit{R.J. Faudree}, \textit{C.C. Rousseau}, and \textit{J. Sheehan}, ``Cycle-book Ramsey numbers,'' Ars Comb. 31, 239--248 (1991; Zbl 0756.05077)], and the Ramsey number of a cycle \(C_{n}\) versus a wheel \(W_{m}=K_{1}*C_{m}\) satisfies \(R(C_{n},W_{m})=2n-1\) for even \(m\) and \(n\geq 3m/2+1\) and \(R(C_{n},W_{m})=3n-2\) for odd \(m>1\) and \(n\geq 3m/2+1\) or \(n>\)max\(\{m+1,70\}\) or \(n\geq\) max\(\{m,83\}\) which improves a result of Surahmat et al. and also confirms their conjecture for large \(n\). As consequences, Ramsey numbers of other sparse graphs are also obtained.
scientific article; zbMATH DE number 5702077
scientific article