Weak saturation numbers of complete bipartite graphs in the clique

Gal Kronenberg, Taísa Martins, Natasha Morrison

Published 2020-04-02Version 1

The notion of weak saturation was introduced by Bollob\'as 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.