Minimizing the numbers of cliques and cycles of fixed size in an F-saturated graph

Abstract This paper considers two important questions in the well-studied theory of graphs that are F -saturated. A graph G is called F -saturated if G does not contain a subgraph isomorphic to F , but the addition of any edge creates a copy of F . We first resolve a fundamental question of minimizing the number of cliques of size r in a K s -saturated graph for all sufficiently large numbers of vertices, confirming a conjecture of Kritschgau, Methuku, Tait, and Timmons. We also go further and prove a corresponding stability result. Next we minimize the number of cycles of length r in a K s -saturated graph for all sufficiently large numbers of vertices, and classify the extremal graphs for most values of r , answering another question of Kritschgau, Methuku, Tait, and Timmons for most r . We then move on to a central and longstanding conjecture in graph saturation made by Tuza, which states that for every graph F , the limit lim n → ∞ sat ( n , F ) n exists, where sat ( n , F ) denotes the minimum number of edges in an n -vertex F -saturated graph. Pikhurko made progress in the negative direction by considering families of graphs instead of a single graph, and proved that there exists a graph family F of size 4 for which lim n → ∞ sat ( n , F ) n does not exist (for a family of graphs F , a graph G is called F -saturated if G does not contain a copy of any graph in F , but the addition of any edge creates a copy of a graph in F , and sat ( n , F ) is defined similarly). We make the first improvement in 15 years by showing that there exist infinitely many graph families of size 3 where this limit does not exist. Our construction also extends to the generalized saturation problem when we minimize the number of fixed-size cliques. We also show an example of a graph F r for which there is irregular behavior in the minimum number of C r ’s in an n -vertex F r -saturated graph.