The saturation number of $K_t^s$

Abstract

For a given graph $F$, a graph $G$ is said to be $F$-saturated if $G$ contains no copy of $F$ but for any edge $uv\notin E(G)$, $G+uv$ contains a copy of $F$. The saturation number $sat(n,F)$ is defined as the minimum number of edges among all $n$-vertex $F$-saturated graphs. The virus graph $K_t^s$, where $s\ge 0$ and $t\ge \max \{3,s\}$, is a graph of order $s+t$ constructed by attaching $s$ distinct leaves to $s$ different vertices of a complete graph $K_t$. Hua and Peng [Discrete Math. 349 (2026) 114674] determined $sat(n,K_3^2)$ and characterized its corresponding extremal graphs. In this paper, we determine $sat(n,K_3^3)$ and $sat(n,K_t^2)$ with $t\ge 4$, together with the structural descriptions of the related extremal saturated graphs.

29 pages,0 figures