The saturation number for unions of four cliques

Abstract

A graph $G$ is $H$-saturated if $H$ is not a subgraph of $G$ but $H$ is a subgraph of $G+e$ for any edge $e$ in $\overline{G}$. The saturation number $sat(n,H)$ for a graph $H$ is the minimal number of edges in any $H$-saturated graph of order $n$. The $sat(n,K_{p_1}\cup K_{p_2}\cup K_{p_3})$ with $p_3\ge p_1+p_2$ was given in [Discrete Math. 347 (2024) 113868]. In this paper, $sat(n,K_{p_1}\cup K_{p_2}\cup K_{p_3}\cup K_{p_4})$ with $p_{i+1}-p_i\ge p_1$ for $2\le i\le 3$ and $4\le p_1\le p_2$ is determined.

17pages