The saturation number of wheels

Yanzhe Qiu; Zhen He; Mei Lu; Yiduo Xu

paper

The saturation number of wheels

arXiv:2503.10268

Abstract

A graph $G$ is said to be $F$ -free, if $G$ does not contain any copy of $F$ . $G$ is said to be $F$ -semi-saturated, if the addition of any nonedge $e \neq \in E (G)$ would create a new copy of $F$ in $G + e$ . $G$ is said to be $F$ -saturated, if $G$ is $F$ -free and $F$ -semi-saturated. The saturation number $s a t (n, F)$ (resp. semi-saturation number $ss a t (n, F)$ ) is the minimum number of edges in an $F$ -saturated (resp. $F$ -semi-saturated) graph of order $n$ . In this paper we proved several results on the (semi)-saturation number of the wheel graph $W_{k} = K_{1} \lor C_{k}$ . Let $k, n$ be positive integers with $k \geq 8$ and $n \geq 56 k^{3}$ , we showed that $(s) s a t (n, W_{k}) = n - 1 + (s) s a t (n - 1, C_{k})$ . We also establish the lower bound of semi-saturation number of $W_{k}$ with restriction on maximum degree.

14 pages