The Rainbow Saturation Number of Cycles

Abstract

An edge-colored graph $(G,\mathcal{C})$ is $F$-rainbow saturated if it contains no rainbow copy of $F$, but adding any nonedge in any prescribed color creates one. The rainbow saturation number $\mathrm{rsat}(n,F)$ is the minimum number of edges in such a graph of order $n$. In this paper we study $\mathrm{rsat}(n,C_r)$. We determine the value for $C_4$ exactly, and establish bounds for every fixed $C_r$ with $r\ge 5$.

arXiv comment15 pages, 4 figures