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

preprint2020arXivOpen access

Abstract

This paper considers two important questions in the well-studied theory of graphs that are FF-saturated. A graph GG is called FF-saturated if GG does not contain a subgraph isomorphic to FF, but the addition of any edge creates a copy of FF. We first resolve a fundamental question of minimizing the number of cliques of size rr in a KsK_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 rr in a KsK_s-saturated graph for all sufficiently large numbers of vertices, and classify the extremal graphs for most values of rr, answering another question of Kritschgau, Methuku, Tait, and Timmons for most rr. We then move on to a central and longstanding conjecture in graph saturation made by Tuza, which states that for every graph FF, the limit $\lim_{n \rightarrow \infty} \frac{\sat(n, F)}{n}$ exists, where $\sat(n, F)$ denotes the minimum number of edges in an nn-vertex FF-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\mathcal{F} of size 44 for which $\lim_{n \rightarrow \infty} \frac{\sat(n, \mathcal{F})}{n}$ does not exist (for a family of graphs F\mathcal{F}, a graph GG is called F\mathcal{F}-saturated if GG does not contain a copy of any graph in F\mathcal{F}, but the addition of any edge creates a copy of a graph in F\mathcal{F}, and $\sat(n, \mathcal{F})$ is defined similarly). We make the first improvement in 15 years by showing that there exist infinitely many graph families of size 33 where this limit does not exist. Our construction also extends to the generalized saturation problem when we minimize the number of fixed-size cliques.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.