Weak saturation numbers of complete bipartite graphs in the clique

Abstract

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,\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 $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.

15 pages, 3 figures

Cited by in corpus (2)

• On the Running Time of Hypergraph Bootstrap Percolation
• Weak saturation of multipartite hypergraphs