Minimizing the number of complete bipartite graphs in a $K_s$-saturated graph
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 793-807
Voir la notice de l'article provenant de la source Library of Science
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 K_1,t in a K_s-saturated graph is Θ ( n^t//2). More precise results are obtained in the case of K_1,2, where determining the minimum number of K_1,2's in a K_3-saturated graph is related to the existence of Moore graphs. We prove that for s ≥ 4 and t ≥ 3, an n-vertex K_s-saturated graph must have at least C n^t//5 + 8//5 copies of K_2,t, and we give an upper bound of O(n^t//2 + 3//2). These results answer a question of Chakraborti and Loh on extremal K_s-saturated graphs that minimize the number of copies of a fixed graph H. General estimates on the number of K_a,b's are also obtained, but finding an asymptotic formula for the number K_a,b's in a K_s-saturated graph remains open.
Keywords:
extremal graph theory, graph saturation
@article{DMGT_2023_43_3_a13,
author = {Ergemlidze, Beka and Methuku, Abhishek and Tait, Michael and Timmons, Craig},
title = {Minimizing the number of complete bipartite graphs in a $K_s$-saturated graph},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {793--807},
publisher = {mathdoc},
volume = {43},
number = {3},
year = {2023},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a13/}
}
TY - JOUR AU - Ergemlidze, Beka AU - Methuku, Abhishek AU - Tait, Michael AU - Timmons, Craig TI - Minimizing the number of complete bipartite graphs in a $K_s$-saturated graph JO - Discussiones Mathematicae. Graph Theory PY - 2023 SP - 793 EP - 807 VL - 43 IS - 3 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a13/ LA - en ID - DMGT_2023_43_3_a13 ER -
%0 Journal Article %A Ergemlidze, Beka %A Methuku, Abhishek %A Tait, Michael %A Timmons, Craig %T Minimizing the number of complete bipartite graphs in a $K_s$-saturated graph %J Discussiones Mathematicae. Graph Theory %D 2023 %P 793-807 %V 43 %N 3 %I mathdoc %U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a13/ %G en %F DMGT_2023_43_3_a13
Ergemlidze, Beka; Methuku, Abhishek; Tait, Michael; Timmons, Craig. Minimizing the number of complete bipartite graphs in a $K_s$-saturated graph. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 793-807. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a13/