A note on the saturation number for unions of three cliques

Abstract

A graph $G$ is $F$-saturated if $G$ contains no copy of $F$ but $G+e$ contains a copy of $F$ for every missing edge $e$ of $G$. The saturation number $\sat(n,F)$ is the minimum number of edges in an $n$-vertex $F$-saturated graph. Motivated by a problem posed by Faudree, Ferrara, Gould, and Jacobson concerning $K_p\cup K_q\cup K_{q+1}$, we determine the saturation number and the unique extremal graph for $K_p\cup K_q\cup K_r$ whenever $2\le p\le q<r<p+q$ and $n$ is sufficiently large. Together with the previously known results for $r\ge p+q$ and for $r=q$, this completes the determination of the saturation number and the extremal graphs for unions of three cliques, for all sufficiently large $n$.

Disclosure

“Acknowledgement The authors used GPT-5.6 to find the proof of Lemma 2.2, and for grammar and style checking. After using this tool, the authors reviewed and edited the content as needed and take full responsibility for the content of the manuscript. The research of He was supp”

PDF page 6

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T19:16:48.203140Z

Structural counts