Asymptotics of Ramsey numbers of double stars

Abstract

A double star $S(n,m)$ is the graph obtained by joining the center of a star with $n$ leaves to a center of a star with $m$ leaves by an edge. Let $r(S(n,m))$ denote the Ramsey number of the double star $S(n,m)$. In 1979 Grossman, Harary and Klawe have shown that $$r(S(n,m))=\max \{n+2m+2,2n+2\}$$ for $3\le m\le n\le \sqrt{2}m$ and $3m\le n$. They conjectured that equality holds for all $m,n\ge 3$. Using a flag algebra computation, we extend their result showing that $r(S(n,m))\le n+2m+2$ for $m\le n\le 1.699m$. On the other hand, we show that the conjecture fails for $\frac{7}{4}m+o(m)\le n\le \frac{105}{41}m-o(m)$. Our examples additionally give a negative answer to a question of Erdős, Faudree, Rousseau and Schelp from 1982.