Contents Online

# Journal of Combinatorics

## Volume 7 (2016)

### Number 1

### Graph saturation in multipartite graphs

Pages: 1 – 19

DOI: http://dx.doi.org/10.4310/JOC.2016.v7.n1.a1

#### Authors

#### 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 $\mathrm{ex}(\mathcal{F},G)$ and $\mathrm{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 $\mathrm{sat}(\mathcal{F},G) = \mathrm{ex}(\mathcal{F},G) = |E(G)|$.

In this paper, for $k \geq 3$ and $n \geq 100$ we determine $\mathrm{sat}(K_3 , K^n_k)$, where $ K^n_k$ 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^n_k$ for $t \geq 4$. Our results and constructions provide an informative contrast to recent results on the edge-density version of $\mathrm{ex}(K_t , K^n_k)$ 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].

#### Keywords

saturated graph, saturation number

#### 2010 Mathematics Subject Classification

05C35

Published 9 December 2015