Few $T$ copies in $H$-saturated graphs

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á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 $\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.

28 pages

References in corpus (1)

• Counting copies of a fixed subgraph in $F$-free graphs

Cited by in corpus (2)

• Minimizing the numbers of cliques and cycles of fixed size in an $F$-saturated graph
• Generalized saturation problems for cliques, paths, and stars