On the saturation spectrum of the unions of disjoint cycles

Abstract

Let $G$ be a graph and $\mathcal{H}$ be a family of graphs. We say $G$ is $\mathcal{H}$-saturated if $G$ does not contain a copy of $H$ with $H\in \mathcal{H}$, but the addition of any edge $e\notin E(G)$ creates at least one copy of some $H\in \mathcal{H}$ within $G+e$. The saturation number of $\mathcal{H}$ is the minimum size of an $\mathcal{H}$-saturated graph on $n$ vertices, and the saturation spectrum of $\mathcal{H}$ is the set of all possible sizes of an $\mathcal{H}$-saturated graph on $n$ vertices. Let $k{\mathcal{C}}_{\ge 3}$ be the family of the unions of $k$ vertex-disjoint cycles. In this note, we completely determine the saturation number and the saturation spectrum of $k{\mathcal{C}}_{\ge 3}$ for $k=2$ and give some results for $k\ge 3$.

24 pages, 4 figures