Ramsey numbers for complete graphs versus generalized fans

Abstract

For two graphs $G$ and $H$, let $r(G,H)$ and $r_{\ast }(G,H)$ denote the Ramsey number and star-critical Ramsey number of $G$ versus $H$, respectively. In 1996, Li and Rousseau proved that $r(K_m,F_{t,n})=tn(m-1)+1$ for $m\ge 3$ and sufficiently large $n$, where $F_{t,n}=K_1+n{K}_t$. Recently, Hao and Lin proved that $r(K_3,F_{3,n})=6n+1$ for $n\ge 3$ and $r_{\ast }(K_3,F_{3,n})=3n+3$ for $n\ge 4$. In this paper, we show that $r(K_m,s{F}_{t,n})=tn(m+s-2)+s$ for sufficiently large $n$ and, in particular, $r(K_3,s{F}_{t,n})=tn(s+1)+s$ for $t\in \{3,4\},n\ge t$ and $s\ge 1$. We also show that $r_{\ast }(K_3,F_{4,n})=4n+4$ for $n\ge 4$ and establish an upper bound on $r(F_{2,m},F_{t,n})$.

arXiv comment9 pages

References in corpus (1)

• Improved bounds on the Ramsey number of fans