Star-Wheel Ramsey Numbers

Abstract

For given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest natural number $n$ such that for every graph $F$ of order $n$: either $F$ contains $G$ or the complement of $F$ contains $H$.

This paper investigates the Ramsey number $R(S_n,W_m)$ of stars versus wheels. We show that if $m$ is odd, $n\ge 3$, and $m\le 2n-1$, then $R(S_n,W_m)=3n-2$. Furthermore, if $n$ is odd and $n\ge 5$, then $R(S_n,W_m)=3n–\mu$, where $\mu =4$ if $m=2n–4$ and $\mu =6$ if $m=2n–8$ or $m=2n–6$.