Minimizing the number of edges in ${\mathcal{C}}_{[4,6]}$-saturated graphs

Abstract

Let ${\mathcal{C}}_{[4,r]}$ be the family of cycles $\{C_4,\dots ,C_r\}$. A graph $G$ is said to be ${\mathcal{C}}_{[4,r]}$-saturated if $G$ does not contain a copy of cycle $C_i$ for $4\le i\le r$, but the addition of any edge $e\notin E(G)$ creates at least one copy of $C_i$ for $4\le i\le r.$ The saturation number $sat(n,{\mathcal{C}}_{[4,r]})$ is the minimum number of edges in an $n$-vertex ${\mathcal{C}}_{[4,r]}$-saturated graph. In 2025, Ma determined that $sat(n,{\mathcal{C}}_{[4,5]})=\lceil \frac{5n}{4}-\frac{3}{2}\rceil$, and conjectured that for any $r\ge 5$, $sat(n,{\mathcal{C}}_{[4,r]})=\lceil \frac{5n}{4}-\frac{3}{2}\rceil$ holds for large $n$. In this paper we prove that $sat(n,{\mathcal{C}}_{[4,r]})\le \lceil \frac{5n}{4}-\frac{r+1}{4}\rceil$ for $n\ge r+1$, which disproves Ma's conjecture for $r\ge 6.$ For $r=6,$ we determine that $sat(n,{\mathcal{C}}_{[4,6]})=\lceil \frac{5n}{4}-\frac{7}{4}\rceil .$ {\bf Keywords}: Saturation graphs; Saturation number; Cycles; Edge minimization

25 pages, 11 figures