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 $iin{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)+binom{r - 2}{2} $ 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 Tofts conjecture for sufficiently large $n$ was setteled in 2011, and is so far the only settled case. Motivated by Hanson and Tofts 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))$.
Download