Graph Saturation in Multipartite Graphs

Abstract

Let $G$ be a fixed graph and let $\mathcal{F}$ be a family of graphs. A subgraph $J$ of $G$ is $\mathcal{F}$-saturated if no member of $\mathcal{F}$ is a subgraph of $J$, but for any edge $e$ in $E(G)-E(J)$, some element of $\mathcal{F}$ is a subgraph of $J+e$. We let $\text{ex}(\mathcal{F},G)$ and $\text{sat}(\mathcal{F},G)$ denote the maximum and minimum size of an $\mathcal{F}$-saturated subgraph of $G$, respectively. If no element of $\mathcal{F}$ is a subgraph of $G$, then $\text{sat}(\mathcal{F},G)=\text{ex}(\mathcal{F},G)=|E(G)|$. In this paper, for $k\ge 3$ and $n\ge 100$ we determine $\text{sat}(K_3,K_k^n)$, where $K_k^n$ is the complete balanced $k$-partite graph with partite sets of size $n$. We also give several families of constructions of $K_t$-saturated subgraphs of $K_k^n$ for $t\ge 4$. Our results and constructions provide an informative contrast to recent results on the edge-density version of $\text{ex}(K_t,K_k^n)$ from [A. Bondy, J. Shen, S. Thomassé, and C. Thomassen, Density conditions for triangles in multipartite graphs, Combinatorica 26 (2006), 121--131] and [F. Pfender, Complete subgraphs in multipartite graphs, Combinatorica 32 (2012), no. 4, 483--495].

16 pages, 4 figures