The reviewed record of science sign in
Pith

arxiv: 2401.11525 · v1 · pith:ZJFDHMAH · submitted 2024-01-21 · math.CO

Weak rainbow saturation numbers of graphs

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:ZJFDHMAHrecord.jsonopen to challenge →

classification math.CO
keywords rainbowgraphlimitaddededgesemphexistsldots
0
0 comments X
read the original abstract

For a fixed graph $H$, we say that an edge-colored graph $G$ is \emph{weakly $H$-rainbow saturated} if there exists an ordering $e_1, e_2, \ldots, e_m$ of $E\left(\overline{G}\right)$ such that, for any list $c_1, c_2, \ldots, c_m$ of pairwise distinct colors from $\mathbb{N}$, the non-edges $e_i$ in color $c_i$ can be added to $G$, one at a time, so that every added edge creates a new rainbow copy of $H$. The \emph{weak rainbow saturation number} of $H$, denoted by $rwsat(n,H)$, is the minimum number of edges in a weakly $H$-rainbow saturated graph on $n$ vertices. In this paper, we show that for any non-empty graph $H$, the limit $\lim_{n\to \infty} \frac{rwsat(n, H)}{n}$ exists. This answers a question of Behague, Johnston, Letzter, Morrison and Ogden [{\it SIAM J. Discrete Math.} (2023)]. We also provide lower and upper bounds on this limit, and in particular, we show that this limit is nonzero if and only if $H$ contains no pendant edges.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.