TY - JOUR
T1 - Minimizing the number of complete bipartite graphs in a ks-saturated graph
AU - Ergemlidze, Beka
AU - Methuku, Abhishek
AU - Tait, Michael
AU - Timmons, Craig
N1 - Publisher Copyright:
© 2021 Beka Ergemlidze et al., published by Sciendo 2021.
PY - 2023
Y1 - 2023
N2 - A graph is F-saturated if it does not contain F as a subgraph but the addition of any edge creates a copy of F. We prove that for s ≥ 3 and t ≥ 2, the minimum number of copies of K1,t in a Ks-saturated graph is Θ (nt/2). More precise results are obtained in the case of K1,2, where determining the minimum number of K1,2's in a K3-saturated graph is related to the existence of Moore graphs. We prove that for s ≥ 4 and t ≥ 3, an n-vertex Ks-saturated graph must have at least Cnt/5+8/5 copies of K2,t, and we give an upper bound of O(nt/2+3/2). These results answer a question of Chakraborti and Loh on extremal Ks-saturated graphs that minimize the number of copies of a fixed graph H. General estimates on the number of Ka,b's are also obtained, but finding an asymptotic formula for the number Ka,b's in a Ks-saturated graph remains open.
AB - A graph is F-saturated if it does not contain F as a subgraph but the addition of any edge creates a copy of F. We prove that for s ≥ 3 and t ≥ 2, the minimum number of copies of K1,t in a Ks-saturated graph is Θ (nt/2). More precise results are obtained in the case of K1,2, where determining the minimum number of K1,2's in a K3-saturated graph is related to the existence of Moore graphs. We prove that for s ≥ 4 and t ≥ 3, an n-vertex Ks-saturated graph must have at least Cnt/5+8/5 copies of K2,t, and we give an upper bound of O(nt/2+3/2). These results answer a question of Chakraborti and Loh on extremal Ks-saturated graphs that minimize the number of copies of a fixed graph H. General estimates on the number of Ka,b's are also obtained, but finding an asymptotic formula for the number Ka,b's in a Ks-saturated graph remains open.
KW - extremal graph theory
KW - graph saturation
UR - http://www.scopus.com/inward/record.url?scp=85101256575&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85101256575&partnerID=8YFLogxK
U2 - 10.7151/dmgt.2402
DO - 10.7151/dmgt.2402
M3 - Article
AN - SCOPUS:85101256575
SN - 1234-3099
VL - 43
SP - 793
EP - 807
JO - Discussiones Mathematicae - Graph Theory
JF - Discussiones Mathematicae - Graph Theory
IS - 3
ER -