Restricted size Ramsey number for $P_3$ versus cycles

Abstract

Let $F$, $G$ and $H$ be simple graphs. We say $F\to (G,H)$ if for every $2$-coloring of the edges of $F$ there exists a monochromatic $G$ or $H$ in $F$. The Ramsey number $r(G,H)$ is defined as $r(G,H)=min\{|V(F)|:F\to (G,H)\}$, while the restricted size Ramsey number $r^{\ast }(G,H)$ is defined as $r^{\ast }(G,H)=min\{|E(F)|:F\to (G,H),|V(F)|=r(G,H)\}$. In this paper we determine previously unknown restricted size Ramsey numbers $r^{\ast }(P_3,C_n)$ for $7\le n\le 12$. We also give new upper bound $r^{\ast }(P_3,C_n)\le 2n-2$ for even $n\ge 8$.