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

DOI10.1016/J.EJC.2020.103185zbMATH Open1458.05111arXiv1907.01603OpenAlexW3042915511MaRDI QIDQ2225397FDOQ2225397

Authors: Debsoumya Chakraborti, Po-Shen Loh 

Publication date: 8 February 2021

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

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.

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

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

zbMATH Keywords

\(F\)-free graphTuran number

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

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

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)