Narrowing down the gap on cycle-star Ramsey numbers

Given two graphs $G_1$ and $G_2$, the Ramsey number $R(G_1, G_2)$ is the smallest integer $N$ such that, for any graph $G$ of order $N$, either $G_1$ is a subgraph of $G$, or $G_2$ is a subgraph of the complement of $G$. Let $C_m$ denote a cycle of order $m$, $K_{1,n}$ a star of order $n+1$ and $W_n$ a wheel of order $n+1$. Already back in the 1970s, exact values of the Ramsey numbers $R(C_m,K_{1,n})$ have been determined for all $m\geq2n$ and for all odd $m\leq2n-1$, but for even $m< 2n$ not many exact values are known. In this paper, we use a result of Bondy on pancyclicity to fill a considerable part of this gap. We show that $R(C_m,K_{1,n})=2n$ for even $m$ with $n<m< 2n$, and that $R(C_m,K_{1,n})=2m-1$ for even $m$ with $3n/4+1\leq m\leq n$. In addition, we determine another six formerly unknown exact values of Ramsey numbers, namely $R(C_6,K_{1,n})$ for $7\leq n\leq11$, and $R(C_6,W_9)$.

Keywords

Ramsey number, cycle, star

2010 Mathematics Subject Classification

Primary 05C55. Secondary 05D10.

Full Text (PDF format)

Published 23 February 2016