Few H copies in F ‐saturated graphs

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 = 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 sat ( n , H , F ) = Θ ( n m ) . (b) For many pairs k and l , we show 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) sat ( n , K 3 , K 4 ) = n − 2 , sat ( n , C 4 , K 4 ) ∼ n 2 2 , and sat ( n , C 6 , K 5 ) ∼ n 3 . We discuss several intriguing problems that remain unsolved.