Few H copies in F-saturated graphs

Abstract

© 2019 Wiley Periodicals, Inc. 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 Turan 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: For any natural number m, there are graphs H and F such that sat(n,H,F)=Theta(nm). 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. sat(n,K3,K4)=n-2, sat(n,C4,K4)similar to n22, and sat(n,C6,K5)similar to n3. (a)(b)(c) We discuss several intriguing problems that remain unsolved