The weak saturation number of ${\mathbf{K}}_{2,\mathbf{t}}$

Abstract

For two graphs $G$ and $F$, we say that $G$ is weakly $F$-saturated if $G$ contains no copy of $F$ as a subgraph and one could join all the nonadjacent pairs of vertices of $G$ in some order so that a new copy of $F$ is created at each step. The weak saturation number $\mathrm{wsat}(n,F)$ is the minimum number of edges of a weakly $F$-saturated graph on $n$ vertices. In this paper, we examine $\mathrm{wsat}(n,K_{s,t})$, where $K_{s,t}$ is the complete bipartite graph with parts of sizes $s$ and $t$. We determine $\mathrm{wsat}(n,K_{2,t})$, correcting a previous report in the literature. It is also shown that $\mathrm{wsat}(s+t,K_{s,t})=\left(\genfrac{}{}{0ex}{}{s+t-1}{2}\right)$ if $\gcd (s,t)=1$ and $\mathrm{wsat}(s+t,K_{s,t})=\left(\genfrac{}{}{0ex}{}{s+t-1}{2}\right)+1$, otherwise.