Saturation numbers for Ramsey-minimal graphs

Abstract

Given graphs $H_1,\dots ,H_t$, a graph $G$ is $(H_1,\dots ,H_t)$-Ramsey-minimal if every $t$-coloring of the edges of $G$ contains a monochromatic $H_i$ in color $i$ for some $i\in \{1,\dots ,t\}$, but any proper subgraph of $G$ does not possess this property. We define ${\mathcal{R}}_{\min }(H_1,\dots ,H_t)$ to be the family of $(H_1,\dots ,H_t)$-Ramsey-minimal graphs. A graph $G$ is \dfn{${\mathcal{R}}_{\min }(H_1,\dots ,H_t)$-saturated} if no element of ${\mathcal{R}}_{\min }(H_1,\dots ,H_t)$ is a subgraph of $G$, but for any edge $e$ in $\overline{G}$, some element of ${\mathcal{R}}_{\min }(H_1,\dots ,H_t)$ is a subgraph of $G+e$. We define $sat(n,{\mathcal{R}}_{\min }(H_1,\dots ,H_t))$ to be the minimum number of edges over all ${\mathcal{R}}_{\min }(H_1,\dots ,H_t)$-saturated graphs on $n$ vertices. In 1987, Hanson and Toft conjectured that $sat(n,{\mathcal{R}}_{\min }(K_{k_1},\dots ,K_{k_t}))=(r-2)(n-r+2)+\left(\genfrac{}{}{0ex}{}{r-2}{2}\right)$ for $n\ge r$, where $r=r(K_{k_1},\dots ,K_{k_t})$ is the classical Ramsey number for complete graphs. The first non-trivial case of Hanson and Toft's conjecture for sufficiently large $n$ was setteled in 2011, and is so far the only settled case. Motivated by Hanson and Toft's conjecture, we study the minimum number of edges over all ${\mathcal{R}}_{\min }(K_3,{\mathcal{T}}_k)$-saturated graphs on $n$ vertices, where ${\mathcal{T}}_k$ is the family of all trees on $k$ vertices. We show that for $n\ge 18$, $sat(n,{\mathcal{R}}_{\min }(K_3,{\mathcal{T}}_4))=\lfloor 5n/2\rfloor$. For $k\ge 5$ and $n\ge 2k+(\lceil k/2\rceil +1)\lceil k/2\rceil -2$, we obtain an asymptotic bound for $sat(n,{\mathcal{R}}_{\min }(K_3,{\mathcal{T}}_k))$.

to appear in Discrete Mathematics