×

Weak saturation numbers of complete bipartite graphs in the clique. (English) Zbl 1457.05089

Summary: The notion of weak saturation was introduced by B. Bollobas [in: Beiträge zur Graphentheorie. Vorgetragen auf dem internationalen Kolloquium in Manebach (DDR) vom 9.–12. Mai 1967. Leipzig: B.G. Teubner Verlagsgesellschaft. 25–31 (1968; Zbl 0172.48905)]. Let \(F\) and \(H\) be graphs. A spanning subgraph \(G\subseteq F\) is weakly \((F, H)\)-saturated if it contains no copy of \(H\) but there exists an ordering \(e_1,\dots,e_t\) of \(E(F)\setminus E(G)\) such that for each \(i\in [t]\), the graph \(G\cup\{ e_1,\dots,e_i\}\) contains a copy \(H^\prime\) of \(H\) such that \(e_i \in H^\prime\). Define \(\operatorname{wsat}(F,H)\) to be the minimum number of edges in a weakly \((F, H)\)-saturated graph. In this paper, we prove for all \(t \geq 2\) and \(n\geq 3t-3\), that \(\operatorname{wsat}(K_n,K_{t,t})=(t-1)(n+1-t/2)\), and we determine the value of \(\operatorname{wsat}( K_n, K_{t-1,t})\) as well. For fixed \(2\leq s<t\), we also obtain bounds on \(\operatorname{wsat}( K_n, K_{s , t})\) that are asymptotically tight.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory

Citations:

Zbl 0172.48905
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N., An extremal problem for sets with applications to graph theory, J. Comb. Theory, Ser. A, 40, 82-89 (1985) · Zbl 0578.05002
[2] Balogh, J.; Bollobás, B.; Morris, R.; Riordan, O., Linear algebra and bootstrap percolation, J. Comb. Theory, Ser. A, 119, 1328-1335 (2012) · Zbl 1242.05190
[3] Balogh, J.; Pete, G., Random disease on the square grid, Random Struct. Algorithms, 13, 409-422 (1998) · Zbl 0964.60006
[4] Bollobás, B., On generalized graphs, Acta Math., 16, 447-452 (1965) · Zbl 0138.19404
[5] Bollobás, B., Weakly k-saturated graphs, Beitr. Graphentheorie, 25-31 (1968) · Zbl 0172.48905
[6] Borowiecki, M.; Sidorowicz, E., Weakly P-saturated graphs, Discuss. Math., Graph Theory, 22, 17-29 (2002) · Zbl 1016.05044
[7] Erdős Füredi, P.; Tuza, Z., Saturated r-uniform hypergraphs, Discrete Math., 98, 95-104 (1991) · Zbl 0766.05060
[8] Faudree, J. R.; Faudree, R. J.; Schmitt, J. R., A survey of minimum saturated graphs, Electron. J. Comb., 1000, 19-29 (2011) · Zbl 1222.05113
[9] Faudree, R. J.; Gould, R. J., Weak saturation numbers for multiple copies, Discrete Math., 336, 1-6 (2014) · Zbl 1297.05119
[10] Faudree, R. J.; Gould, R. J.; Jacobson, M. S., Weak saturation numbers for sparse graphs, Discuss. Math., Graph Theory, 33, 677-693 (2013) · Zbl 1295.05130
[11] Frankl, P., An extremal problem for two families of sets, Eur. J. Comb., 3, 125-127 (1982) · Zbl 0488.05004
[12] Kalai, G., Hyperconnectivity of graphs, Graphs Comb., 1, 65-79 (1985) · Zbl 0609.05051
[13] Kalai, G., Weakly saturated graphs are rigid, North-Holl. Math. Stud., 87, 189-190 (1984) · Zbl 0576.05018
[14] Lovász, L., Flats in matroids and geometric graphs, (Combinatorial Surveys (1977)), 45-86 · Zbl 0361.05027
[15] Morrison, N.; Noel, J. A., A sharp threshold for bootstrap percolation in a random hypergraph, available as · Zbl 1479.60199
[16] Morrison, N.; Noel, J. A., Extremal bounds for bootstrap percolation in the hypercube, J. Comb. Theory, Ser. A, 156, 61-84 (2018) · Zbl 1381.05072
[17] Moshkovitz, G.; Shapira, A., Exact bounds for some hypergraph saturation problems, J. Comb. Theory, Ser. B, 111, 242-248 (2015) · Zbl 1307.05167
[18] Pikhurko, O., Uniform families and count matroids, Graphs Comb., 17, 729-740 (2001) · Zbl 0987.05060
[19] Pikhurko, O., Weakly saturated hypergraphs and exterior algebra, Comb. Probab. Comput., 10, 435-451 (2001) · Zbl 1002.05053
[20] Semanišin, G., On some variations of extremal graph problems, Discuss. Math., Graph Theory, 17, 67-76 (1997) · Zbl 0904.05046
[21] Sidorowicz, E., Size of weakly saturated graphs, Discrete Math., 307, 1486-1492 (2007) · Zbl 1118.05046
[22] Tuza, Z., Asymptotic growth of sparse saturated structures is locally determined, Discrete Math., 108, 397-402 (1992) · Zbl 0767.05064
[23] Tuza, Z., Extremal problems on saturated graphs and hypergraphs, Ars Comb., 25, 105-113 (1988) · Zbl 0662.05030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.