Some results on the saturation number for unions of cliques

Fan Chen; Xiying Yuan

paper

Some results on the saturation number for unions of cliques

arXiv:2303.11893

Abstract

Graph $G$ is $H$ -saturated if $H$ is not a subgraph of $G$ and $H$ is a subgraph of $G + e$ for any edge $e$ not in $G$ . The saturation number for a graph $H$ is the minimal number of edges in any $H$ -saturated graph of order $n$ . In this paper, the saturation number for $K_{p} \cup (t - 1) K_{q}$ ( $t ⩾ 3$ and $2 ⩽ p < q$ ) is determined, and the extremal graph for $K_{p} \cup 2 K_{q}$ is determined. Moreover, the saturation number and the extremal graph for $K_{p} \cup K_{q} \cup K_{r}$ ( $r ⩾ p + q$ ) are completely determined.