Saturation numbers in tripartite graphs
read the original abstract
Given graphs $H$ and $F$, a subgraph $G\subseteq H$ is an $F$-saturated subgraph of $H$ if $F\nsubseteq 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$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.