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 function sat(n,H,F) which is the minimum number of copies of H that an F‐saturated graph on n vertices may contain. This function is a natural saturation analogue of Alon and Shikhelman's generalized Turán problem, and letting H=K2 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 Ks or Ck‐saturated. Some representative interesting behavior is:
(a)For any natural number m, there are graphs H and F such that sat(n,H,F)=Θ(nm).(b)For many pairs k and l, we show sat(n,Cl,Ck)=0. In particular, we prove that there exists a triangle‐free Ck‐saturated graph on n vertices for any k>4 and large enough n.(c)sat(n,K3,K4)=n−2, sat(n,C4,K4)∼n22, and sat(n,C6,K5)∼n3. We discuss several intriguing problems that remain unsolved.