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

DOI10.1016/J.EJC.2020.103185MaRDI QIDQ2225397zbMATH OpenOpenAlexFDO

Authors Debsoumya Chakraborti, Po-Shen Loh

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1907.01603

zbMATH Keywords

\(F\)-free graphTuran number

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

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 $li{m}_{nightarrowinfty}fracsat(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 $mathcalF$ of size $4$ for which $li{m}_{nightarrowinfty}fracsat(n,mathcalF)n$ does not exist (for a family of graphs $mathcalF$, a graph $G$ is called $mathcalF$-saturated if $G$ does not contain a copy of any graph in $mathcalF$, but the addition of any edge creates a copy of a graph in $mathcalF$, and $sat(n,mathcalF)$ 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.

Recommendations

• Asymptotic results on saturated graphs
• Minimum C_k-saturated graphs
• Minimizing the number of edges in \(\mathcal{C}_{\geq r} \)-saturated graphs
• scientific article; zbMATH DE number 4081590
• Few \(H\) copies in \(F\)-saturated graphs

Cites work

• A Problem in Graph Theory
• A survey of minimum saturated graphs
• Asymptotic growth of sparse saturated structures is locally determined
• Asymptotic results on saturated graphs
• Constructing designs straightforwardly: Worst arising cases
• Few \(H\) copies in \(F\)-saturated graphs
• scientific article; zbMATH DE number 4081590 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• scientific article; zbMATH DE number 2192110 (Why is no real title available?)
• scientific article; zbMATH DE number 3185004 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• Many \(T\) copies in \(H\)-free graphs
• On complete subgraphs of different orders
• On generalized graphs
• On the non-(p-1)-partite K_p-free graphs
• Saturated graphs with minimal number of edges
• Size in maximal triangle-free graphs and minimal graphs of diameter 2
• Supersaturated graphs and hypergraphs
• The history of degenerate (bipartite) extremal graph problems
• The saturation function of complete partite graphs
• What we know and what we do not know about Turán numbers

Cited in

(16)

• Asymptotic results on saturated graphs
• Hypergraph saturation irregularities
• Cycle-saturated graphs of minimum size
• Uniquely \(K_r\)-saturated graphs
• Saturation numbers for disjoint stars
• The minimum number of clique-saturating edges
• Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
• Onk-saturated graphs with restrictions on the degrees
• Minimizing the number of edges in \(K_{(s,t)}\)-saturated bipartite graphs
• Few \(H\) copies in \(F\)-saturated graphs
• Weakly saturated hypergraphs and a conjecture of Tuza
• Constructive upper bounds for cycle-saturated graphs of minimum size
• Rainbow Saturation for Complete Graphs
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Generalized saturation game
• Minimizing the number of complete bipartite graphs in a K_s-saturated graph

This page was built for publication: Minimizing the numbers of cliques and cycles of fixed size in an \(F\)-saturated graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225397)