Weak rainbow saturation numbers of paths, stars and cycles
Abstract
An edge-colored graph is \emph{rainbow} if all of its edges receive distinct colors. For a fixed graph H, an edge-colored graph F is called weakly H-rainbow saturated if there exists an ordering e1,e2,…,e|E(F̅)| of E(F̅) such that, for any edge coloring c of E(F̅) with c(ei)≠ c(ej), there is always a rainbow copy of H that contains ei in F+{e1,e2,…,ei}. The \emph{weak rainbow saturation number} rwsat(n,H) is the minimum number of edges in a weakly H-rainbow saturated graph on n vertices. Li, Ma, and Xie [JGT, 2025] showed that limn→∞ rwsat(n,H)/n exists for every nonempty graph H. Paths and stars attain, respectively, the minimum and maximum ordinary weak saturation numbers among all trees of the same order. We determine their weak rainbow saturation numbers exactly. For all ℓ>30, we show that ℓ+1=s(n,Pℓ)< s(n,Sℓ)=binomℓ2−1 where Pℓ and Sℓ denote the path and star on ℓ vertices, respectively. Thus, their dependence on ℓ is linear for paths and quadratic for stars. We then focus on cycles. Li, Ma, and Xie asked whether rwsat(n,Cℓ) has leading term 3/2n for every ℓ≥4. We answer this question negatively by giving an explicit construction showing that, for every ℓ≥4 and all sufficiently large n, s(n,Cℓ)< ℓ/(ℓ−1)n+cℓ, where cℓ depends only on ℓ. Since ℓ/(ℓ−1)<3/2, this strictly improves the proposed leading coefficient for every cycle Cℓ with ℓ≥4.
Related
BibTeX
@misc{bo2026weak,
title = {{Weak rainbow saturation numbers of paths, stars and cycles}},
author = {Jiawen Bo and Xiaopan Lian and Jianing Liu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03823},
eprint = {2609.03823},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03823},
}
RIS
TY - UNPB
TI - Weak rainbow saturation numbers of paths, stars and cycles
AU - Jiawen Bo
AU - Xiaopan Lian
AU - Jianing Liu
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03823
UR - https://arxiv.org/abs/2609.03823
AB - An edge-colored graph is \emph{rainbow} if all of its edges receive distinct colors. For a fixed graph H, an edge-colored graph F is called weakly H-rainbow saturated if there exists an ordering e_1,e_2,…,e_|E(F̅)| of E(F̅) such that, for any edge coloring c of E(F̅) with c(e_i)≠ c(e_j), there is always a rainbow copy of H that contains e_i in F+{e_1,e_2,…,e_i}. The \emph{weak rainbow saturation number} rwsat(n,H) is the minimum number of edges in a weakly H-rainbow saturated graph on n vertices. Li, Ma, and Xie [JGT, 2025] showed that lim_n→∞ rwsat(n,H)/n exists for every nonempty graph H. Paths and stars attain, respectively, the minimum and maximum ordinary weak saturation numbers among all trees of the same order. We determine their weak rainbow saturation numbers exactly. For all ℓ>30, we show that ℓ+1=s(n,P_ℓ)< s(n,S_ℓ)=binomℓ2−1 where P_ℓ and S_ℓ denote the path and star on ℓ vertices, respectively. Thus, their dependence on ℓ is linear for paths and quadratic for stars. We then focus on cycles. Li, Ma, and Xie asked whether rwsat(n,C_ℓ) has leading term 3/2n for every ℓ≥4. We answer this question negatively by giving an explicit construction showing that, for every ℓ≥4 and all sufficiently large n, s(n,C_ℓ)< ℓ/(ℓ−1)n+c_ℓ, where c_ℓ depends only on ℓ. Since ℓ/(ℓ−1)<3/2, this strictly improves the proposed leading coefficient for every cycle C_ℓ with ℓ≥4.
ER -