Journal of Combinatorics

Volume 7 (2016)

Number 1

Graph saturation in multipartite graphs

Pages: 1 – 19

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

Authors

Michael Ferrara (Department of Mathematical and Statistical Sciences, University of Colorado, Denver, Co., U.S.A.)

Michael S. Jacobson (Department of Mathematical and Statistical Sciences, University of Colorado, Denver, Co., U.S.A.)

Florian Pfender (Department of Mathematical and Statistical Sciences, University of Colorado, Denver, Co., U.S.A.)

Paul S. Wenger (School of Mathematical Sciences, Rochester Institute of Technology, Rochester, New York, U.S.A.)

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

Full Text (PDF format)

Published 9 December 2015