Weak rainbow saturation numbers of graphs

Abstract

For a fixed graph $H$, we say that an edge-colored graph $G$ is \emph{weakly $H$-rainbow saturated} if there exists an ordering $e_1,e_2,\dots ,e_m$ of $E\left(\overline{G}\right)$ such that, for any list $c_1,c_2,\dots ,c_m$ of pairwise distinct colors from $\mathbb{N}$, the non-edges $e_i$ in color $c_i$ can be added to $G$, one at a time, so that every added edge creates a new rainbow copy of $H$. The \emph{weak rainbow saturation number} of $H$, denoted by $rwsat(n,H)$, is the minimum number of edges in a weakly $H$-rainbow saturated graph on $n$ vertices. In this paper, we show that for any non-empty graph $H$, the limit ${\lim }_{n\to \infty }\frac{rwsat(n,H)}{n}$ exists. This answers a question of Behague, Johnston, Letzter, Morrison and Ogden [{\it SIAM J. Discrete Math.} (2023)]. We also provide lower and upper bounds on this limit, and in particular, we show that this limit is nonzero if and only if $H$ contains no pendant edges.

13 pages, 1 figure