Article in volume
Authors:
Title:
Minimizing the number of complete bipartite graphs in a $K_s$-saturated graph
PDFSource:
Discussiones Mathematicae Graph Theory 43(3) (2023) 793-807
Received: 2021-01-02 , Revised: 2021-03-14 , Accepted: 2021-03-15 , Available online: 2021-04-21 , https://doi.org/10.7151/dmgt.2402
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 \geq 3$ and
$t \geq 2$, the minimum number of copies of $K_{1,t}$ in a $K_s$-saturated
graph is $\Theta ( 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 \geq 4$ and $t \geq 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
References:
- 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:1<1::AID-JGT1>3.0.CO;2-O - 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 - 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 - B. Bollobás and O. Riordan, Constrained graph processes, Electron. J. Combin. 7 (2000) #R18.
https://doi.org/10.37236/1496 - 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 - B. Cole, A. Curry, D. Davini and C. Timmons, Triangles in $K_s$-saturated graphs with minimum degree $t$, Theory Appl. Graphs 7(1) (2020) Article 2.
https://doi.org/10.20429/tag.2020.070102 - 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 - A.N. Day, Saturated graphs of prescribed minimum degree, Combin. Probab. Comput. 26 (2017) 201–207.
https://doi.org/10.1017/S0963548316000377 - 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 - P. Erdős and M. Simonovits, Supersaturated graphs and hypergraphs, Combinatorica 3 (1983) 181–192.
https://doi.org/10.1007/BF02579292 - 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 - 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 - 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 - R.J. Gould and J.R. Schmitt, Minimum degree and the minimum size of $K_2^t$-saturated graphs, Discrete Math. 307 (2007) 1108–1114.
https://doi.org/10.1016/j.disc.2006.08.004 - R.L. Graham, M. Grötschel and L. Lovász, Handbook of Combinatorics, Vol. 2 ({Elsevier, Amsterdam}, 1995).
- D. Hanson and K. Seyffarth, $k$-saturated graphs of prescribed maximum degree, Congr. Numer. 42 (1984) 169–182.
- J. Kim, S. Kim, A. Kostochka and S. O, $K_{r+1}$-saturated graphs with small spectral radius (2020).
arXiv: 2006.04355v1 - 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 - 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:1<61::AID-RSA5>3.0.CO;2-T - O. Pikhurko, Results and open problems on minimum saturated graphs, Ars Combin. 72 (2004) 111–127.
- 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 - J.H. Spencer, Maximal triangle-free graphs and Ramsey $R(3,t)$ (1995), unpublished manuscript.
Close