1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Minimizing the Number of Complete Bipartite Graphs in a Ks-Saturated Graph

Published Online: 05 May 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 02 Jan 2021
Accepted: 15 Mar 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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.

Keywords

MSC 2010

[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. doi:10.1002/(SICI)1097-0118(199609)23:1〈1::AID-JGT1〉3.0.CO;2-OSearch in Google Scholar

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

[3] T. Bohman and P. Keevash, The early evolution of the H-free process, Invent. Math. 181 (2010) 291–336. doi:10.1007/s00222-010-0247-x10.1007/s00222-010-0247-xSearch in Google Scholar

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

[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. doi:10.1016/j.ejc.2020.10318510.1016/j.ejc.2020.103185Search in Google Scholar

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

[7] A.N. Day, Saturated graphs of prescribed minimum degree, Combin. Probab. Comput. 26 (2017) 201–207. doi:10.1017/S096354831600037710.1017/S0963548316000377Search in Google Scholar

[8] D. Duffus and D. Hanson, Minimal k-saturaated and color critical graphs of prescribed minimum degree, J. Graph Theory 10 (1986) 55–67. doi:10.1002/jgt.319010010910.1002/jgt.3190100109Search in Google Scholar

[9] P. Erdős and M. Simonovits, Supersaturated graphs and hypergraphs, Combinatorica 3 (1983) 181–192. doi:10.1007/BF0257929210.1007/BF02579292Search in Google Scholar

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

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

[12] J.R. Faudree, R.J. Faudree and J.R. Schmitt, A survey of minimum saturated graphs, Electron. J. Combin., Dynamic Surveys (2011) #DS19. doi:10.37236/4110.37236/41Search in Google Scholar

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

[14] R.J. Gould and J.R. Schmitt, Minimum degree and the minimum size of Kt2-saturated graphs, Discrete Math. 307 (2007) 1108–1114. doi:10.1016/j.disc.2006.08.00410.1016/j.disc.2006.08.004Search in Google Scholar

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

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

[17] J. Kim, S. Kim, A. Kostochka and S. O, Kr+1-saturated graphs with small spectral radius. arXiv:2006.04355v1 Jun 2020Search in Google Scholar

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

[19] D. Osthus and A. Taraz, Random maximal H-free graphs, Random Structures Algorithms 18 (2001) 61–82. doi:10.1002/1098-2418(200101)18:1〈61::AID-RSA5〉3.0.CO;2-TSearch in Google Scholar

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

[21] A. Rucinski and N. Wormald, Random graph processes with degree restrictions, Combin. Probab. Comput. 1 (1992) 169–180. doi:10.1017/S096354830000018310.1017/S0963548300000183Search in Google Scholar

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo