On rainbow saturated graphs with minimum number of edges
Abstract
Let F be a fixed graph without isolated vertices. An edge-colored graph is F-rainbow saturated if it contains no rainbow copy of F, but the addition of any missing edge in any color creates a rainbow copy of F. The rainbow saturation number $rsat(n,F)$ is the minimum number of edges in such a graph on n vertices. We prove a dichotomy governed by isolated edges: if F contains an isolated edge, then rsat(n,F)=O(1) for all sufficiently large n, while if F has no isolated edge, then rsat(n,F)=Θ(n). The linear lower bound is expressed in terms of a directed weight parameter η(F) and establishes the linear half of the dichotomy; in several cases it also strengthens the Cameron--Puleo type coefficient. For the bounded half, we construct rainbow saturated graphs for targets of the form H∪ K2. As an application of these constructions, we determine the asymptotically tight behavior for the rainbow saturation number of the generalized friendship graph Ft,p,q=tKp∨ Kq, proving that $ rsat(n,F_{t,p,q})=(p+q-1)n+O(1)$ for fixed t≥ 2, p≥ 2 and q≥ 1 as n→∞.
Related
BibTeX
@misc{qiu2026rainbow,
title = {{On rainbow saturated graphs with minimum number of edges}},
author = {Yanzhe Qiu and Mei Lu and Yilin Pan and Yiduo Xu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34898},
eprint = {2609.34898},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34898},
}
RIS
TY - UNPB
TI - On rainbow saturated graphs with minimum number of edges
AU - Yanzhe Qiu
AU - Mei Lu
AU - Yilin Pan
AU - Yiduo Xu
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.34898
UR - https://arxiv.org/abs/2609.34898
AB - Let F be a fixed graph without isolated vertices. An edge-colored graph is F-rainbow saturated if it contains no rainbow copy of F, but the addition of any missing edge in any color creates a rainbow copy of F. The rainbow saturation number $rsat(n,F)$ is the minimum number of edges in such a graph on n vertices. We prove a dichotomy governed by isolated edges: if F contains an isolated edge, then rsat(n,F)=O(1) for all sufficiently large n, while if F has no isolated edge, then rsat(n,F)=Θ(n). The linear lower bound is expressed in terms of a directed weight parameter η(F) and establishes the linear half of the dichotomy; in several cases it also strengthens the Cameron--Puleo type coefficient. For the bounded half, we construct rainbow saturated graphs for targets of the form H∪ K_2. As an application of these constructions, we determine the asymptotically tight behavior for the rainbow saturation number of the generalized friendship graph F_t,p,q=tK_p∨ K_q, proving that $ rsat(n,F_{t,p,q})=(p+q-1)n+O(1)$ for fixed t≥ 2, p≥ 2 and q≥ 1 as n→∞.
ER -