Geodesic
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/