Few H copies in F-saturated graphs

DOI10.1002/JGT.22525zbMATH Open1485.05085arXiv1810.00939OpenAlexW2989984979MaRDI QIDQ5066892FDOQ5066892

Authors: Jürgen Kritschgau, Abhishek Methuku, Michael Tait, Craig Timmons 

Publication date: 31 March 2022

Published in: Journal of Graph Theory (Search for Journal in Brave)

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 $mathrmsat(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'an 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 $mathrmsat(n,H,F)=Theta(n^m)$. (b) For many pairs $k$ and $l$, we show $mathrmsat(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) $mathrmsat(n,K_3,K_4)=n-2$, $mathrmsat(n,C_4,K_4)simfrac{n}^{2}2$, and $mathrmsat(n,C_6,K_5)sim{n}^3$. We discuss several intriguing problems which remain unsolved.

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

Recommendations

• \(C_{2k}\)-saturated graphs with no short odd cycles
• Minimum \(C_k\)-saturated graphs
• Minimizing the numbers of cliques and cycles of fixed size in an \(F\)-saturated graph
• scientific article; zbMATH DE number 4185643
• The saturation function of complete partite graphs

zbMATH Keywords

extremal graph theorygraph saturation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cited In (7)

• \(C_{2k}\)-saturated graphs with no short odd cycles
• Graph cover-saturation
• Saturation of Ordered Graphs
• Regular saturated graphs and sum-free sets
• Minimizing the numbers of cliques and cycles of fixed size in an \(F\)-saturated graph
• Minimizing the number of edges in \(K_{(s,t)}\)-saturated bipartite graphs
• Rainbow Saturation for Complete Graphs

This page was built for publication: Few \(H\) copies in \(F\)-saturated graphs

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