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 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2023},
     volume = {43},
     number = {3},
     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
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
%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/

[1] N. Alon, P. Erdős, R. Holzman and M. Krivelevich, On k-saturated graphs with restrictions on the degrees, J. Graph Theory 23 (1996) 1–20. https://doi.org/10.1002/(SICI)1097-0118(199609)23:13.0.CO;2-O

[2] N. Alon and C. Shikhelman, Many T copies in H-free graphs, J. Combin. Theory Ser. B 121 (2016) 146–172. https://doi.org/10.1016/j.jctb.2016.03.004

[3] T. Bohman and P. Keevash, The early evolution of the H-free process, Invent. Math. 181 (2010) 291–336. https://doi.org/10.1007/s00222-010-0247-x

[4] B. Bollobás and O. Riordan, Constrained graph processes, Electron. J. Combin. 7 (2000) #R18. https://doi.org/10.37236/1496

[5] D. Chakraborti and P.-S. Loh, Minimizing the numbers of cliques and cycles of fixed size in an F-saturated graph, European J. Combin. 90 (2020) 103185. https://doi.org/10.1016/j.ejc.2020.103185

[6] B. Cole, A. Curry, D. Davini and C. Timmons, Triangles in Ks-saturated graphs with minimum degree t, Theory Appl. Graphs 7(1) (2020) Article 2. https://doi.org/10.20429/tag.2020.070102

[7] B.L. Curie, J.R. Faudree, R.J. Faudree and J.R. Schmitt, A survey of minimum saturated graphs, Electron. J. Combin., Dynamic Surveys (2011) #DS19 (2021). https://doi.org/10.37236/41

[8] A.N. Day, Saturated graphs of prescribed minimum degree, Combin. Probab. Comput. 26 (2017) 201–207. https://doi.org/10.1017/S0963548316000377

[9] D. Duffus and D. Hanson, Minimal k-saturaated and color critical graphs of prescribed minimum degree, J. Graph Theory 10 (1986) 55–67. https://doi.org/10.1002/jgt.3190100109

[10] P. Erdős and M. Simonovits, Supersaturated graphs and hypergraphs, Combinatorica 3 (1983) 181–192. https://doi.org/10.1007/BF02579292

[11] P. Erdős, A. Hajnal and J.W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964) 1107–1110. https://doi.org/10.2307/2311408

[12] P. Erdős, S. Suen and P. Winkler, On the size of a random maximal graph, Random Structures Algorithms 6 (1995) 309–318. https://doi.org/10.1002/rsa.3240060217

[13] Z. Füredi and A. Seress, Maximal triangle-free graphs with restrictions on the degrees, J. Graph Theory 18 (1994) 11–24. https://doi.org/10.1002/jgt.3190180103

[14] R.J. Gould and J.R. Schmitt, Minimum degree and the minimum size of K2t-saturated graphs, Discrete Math. 307 (2007) 1108–1114. https://doi.org/10.1016/j.disc.2006.08.004

[15] R.L. Graham, M. Grötschel and L. Lovász, Handbook of Combinatorics, Vol. 2 ({Elsevier, Amsterdam}, 1995).

[16] D. Hanson and K. Seyffarth, k-saturated graphs of prescribed maximum degree, Congr. Numer. 42 (1984) 169–182.

[17] J. Kim, S. Kim, A. Kostochka and S. O, Kr+1-saturated graphs with small spectral radius (2020). arXiv: 2006.04355v1

[18] J. Kritschgau, A. Methuku, M. Tait and C. Timmons, Few H copies in F-saturated graphs, J. Graph Theory 94 (2020) 320–348. https://doi.org/10.1002/jgt.22525

[19] D. Osthus and A. Taraz, Random maximal H-free graphs, Random Structures Algorithms 18 (2001) 61–82. https://doi.org/10.1002/1098-2418(200101)18:13.0.CO;2-T

[20] O. Pikhurko, Results and open problems on minimum saturated graphs, Ars Combin. 72 (2004) 111–127.

[21] A. Ruciński and N. Wormald, Random graph processes with degree restrictions, Combin. Probab. Comput. 1 (1992) 169–180. https://doi.org/10.1017/S0963548300000183

[22] J.H. Spencer, Maximal triangle-free graphs and Ramsey R(3,t) (1995), unpublished manuscript.