The Rainbow Saturation Number of Cycles

Abstract

An edge-coloring of a graph $H$ is a function $\mathcal{C}:E(H)\to \mathbb{N}$. We say that $H$ is rainbow if all edges of $H$ have different colors. Given a graph $F$, an edge-colored graph $G$ is $F$-rainbow saturated if $G$ does not contain a rainbow copy of $F$, but the addition of any nonedge with any color on it would create a rainbow copy of $F$. The rainbow saturation number $rsat(n,F)$ is the minimum number of edges in an $F$-rainbow saturated graph with order $n$. In this paper we proved several results on cycle rainbow saturation. For $n\ge 5$, we determined the exact value of $rsat(n,C_4)$. For $n\ge 15$, we proved that $\frac{3}{2}n-\frac{5}{2}\le rsat(n,C_5)\le 2n-6$. For $r\ge 6$ and $n\ge r+3$, we showed that $\frac{6}{5}n\le rsat(n,C_r)\le 2n+O(r^2)$. Moreover, we establish better lower bound on $C_r$-rainbow saturated graph $G$ while $G$ is rainbow.

21pages, 7 figures