Weak saturation numbers of complete bipartite graphs in the clique

• Published in: arXiv.org 2022-03
• Main Authors: Kronenberg, Gal, Martins, Taísa, Morrison, Natasha
• Format: Article
• Language: English
• Subjects: Graph theory; Graphs; Saturation
• ISSN: 2331-8422
• DOI: 10.48550/arxiv.2004.01289

The notion of weak saturation was introduced by Bollobás in 1968. 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,\ldots,e_t\) of \(E(F)\setminus E(G)\) such that for each \(i \in [t]\), the graph \(G \cup \{e_1,\ldots,e_i\}\) contains a copy \(H'\) of \(H\) such that \(e_i \in H'\). Define \(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 \ge 2\) and \(n \ge 3t-3\), that \(wsat(K_n,K_{t,t}) = (t-1)(n + 1 - t/2)\), and we determine the value of \(wsat(K_n,K_{t-1,t})\) as well. For fixed \(2 \le s < t\), we also obtain bounds on \(wsat(K_n,K_{s,t})\) that are asymptotically tight.