The saturation number for unions of four cliques

Ruo-Xuan Li, Rong-Xia Hao, Zhen He, Wen-Han Zhu

Published 2024-08-21Version 1

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.