Abstract
A graph is $F$-saturated if it is $F$-free but the addition of any edge
creates a copy of $F$. In this paper we study the quantity $\mathrm{sat}(n, H,
F)$ which denotes the minimum number of copies of $H$ that an $F$-saturated
graph on $n$ vertices may contain. This parameter is a natural saturation
analogue of Alon and Shikhelman's generalized Tur\'an problem, and letting $H =
K_2$ recovers the well-studied saturation function. We provide a first
investigation into this general function focusing on the cases where the host
graph is either $K_s$ or $C_k$-saturated. Some representative interesting
behavior is:
(a) For any natural number $m$, there are graphs $H$ and $F$ such that
$\mathrm{sat}(n, H, F) = \Theta(n^m)$.
(b) For many pairs $k$ and $l$, we show $\mathrm{sat}(n, C_l, C_k) = 0$. In
particular, we prove that there exists a triangle-free $C_k$-saturated graph on
$n$ vertices for any $k > 4$ and large enough $n$.
(c) $\mathrm{sat}(n, K_3, K_4) = n-2$, $\mathrm{sat}(n, C_4, K_4) \sim
\frac{n^2}{2}$, and $\mathrm{sat}(n, C_6, K_5) \sim n^3$.
We discuss several intriguing problems which remain unsolved.