Saturation numbers in tripartite graphs

Abstract

Given graphs $H$ and $F$, a subgraph $G\subseteq H$ is an $F$-saturated subgraph of $H$ if $F⊈G$, but $F\subseteq G+e$ for all $e\in E(H)\setminus E(G)$. The saturation number of $F$ in $H$, denoted $\text{sat}(H,F)$, is the minimum number of edges in an $F$-saturated subgraph of $H$. In this paper we study saturation numbers of tripartite graphs in tripartite graphs. For $\ell \ge 1$ and $n_1$, $n_2$, and $n_3$ sufficiently large, we determine $\text{sat}(K_{n_1,n_2,n_3},K_{\ell ,\ell ,\ell })$ and $\text{sat}(K_{n_1,n_2,n_3},K_{\ell ,\ell ,\ell -1})$ exactly and $\text{sat}(K_{n_1,n_2,n_3},K_{\ell ,\ell ,\ell -2})$ within an additive constant. We also include general constructions of $K_{\ell ,m,p}$-saturated subgraphs of $K_{n_1,n_2,n_3}$ with few edges for $\ell \ge m\ge p>0$.

18 pages, 6 figures