Ramsey numbers of long cycles versus books or wheels
type: Item
instance of: scholarly article
title: Ramsey numbers of long cycles versus books or wheels
zbMATH Open document ID: 1218.05102
published in: European Journal of Combinatorics
publication date: 2010-04-27T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5702077
author: Lingsheng Shi
MaRDI profile type: Publication
full work available at URL: j.ejc.2009.07.004
OpenAlex ID: W2020235907
cites work: Pancyclic graphs. I
cites work: Q3703921
cites work: Q4889849
cites work: Weakly pancyclic graphs
cites work: Generalizations of a Ramsey-theoretic result of chvátal
cites work: The Ramsey numbers of paths versus wheels
cites work: A note on Hamiltonian circuits
cites work: Generalized Ramsey theory for graphs. III: Small off-diagonal numbers
cites work: Q5315023
cites work: Some Theorems on Abstract Graphs
cites work: Q3981365
cites work: All Ramsey numbers for cycles in graphs
cites work: Q4304331
cites work: On a Ramsey-type problem of J. A. Bondy and P. Erdős. II
cites work: A Class of Ramsey Problems Involving Trees
cites work: On ramsey numbers for books
cites work: On Ramsey numbers for paths versus wheels
cites work: Path-fan Ramsey numbers
cites work: Path-kipas Ramsey numbers
cites work: Q4831480
cites work: On Ramsey numbers for trees versus wheels of five or six vertices
cites work: The Ramsey numbers of large cycles versus odd wheels
cites work: The Ramsey numbers of large cycles versus wheels
cites work: Q4405645
cites work: Q4269454
cites work: Q4367971
DOI: 10.1016/J.EJC.2009.07.004
description: scientific article; zbMATH DE number 5702077