The Rainbow Saturation Number of Cycles
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929672185446400 |
|---|---|
| author | Xu, Yiduo He, Zhen Lu, Mei |
| author_facet | Xu, Yiduo He, Zhen Lu, Mei |
| contents | An edge-coloring of a graph $H$ is a function $\mathcal{C}: E(H) \rightarrow \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 \geq 5$, we determined the exact value of $rsat(n,C_4)$. For $ n \geq 15$, we proved that $\frac{3}{2}n-\frac{5}{2} \leq rsat(n,C_{5}) \leq 2n-6$. For $r \geq 6$ and $n \geq r+3$, we showed that $ \frac{6}{5}n \leq rsat(n,C_r) \leq 2n+O(r^2)$. Moreover, we establish better lower bound on $C_r$-rainbow saturated graph $G$ while $G$ is rainbow. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_06782 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Rainbow Saturation Number of Cycles Xu, Yiduo He, Zhen Lu, Mei Combinatorics 05C35, 05C15 An edge-coloring of a graph $H$ is a function $\mathcal{C}: E(H) \rightarrow \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 \geq 5$, we determined the exact value of $rsat(n,C_4)$. For $ n \geq 15$, we proved that $\frac{3}{2}n-\frac{5}{2} \leq rsat(n,C_{5}) \leq 2n-6$. For $r \geq 6$ and $n \geq r+3$, we showed that $ \frac{6}{5}n \leq rsat(n,C_r) \leq 2n+O(r^2)$. Moreover, we establish better lower bound on $C_r$-rainbow saturated graph $G$ while $G$ is rainbow. |
| title | The Rainbow Saturation Number of Cycles |
| topic | Combinatorics 05C35, 05C15 |
| url | https://arxiv.org/abs/2501.06782 |