Saturation (graph theory)

[[File:C4-saturated graph.svg|thumb|A complete [[multipartite|Template:Mvar-partite graph]], which is [[cycle graph|Template:Mvar]]-saturated]]

In extremal graph theory, given a graph $H$, a graph $G$ is said to be $H$-saturated if $G$ does not contain a copy of $H$ as a subgraph, but adding any edge to $G$ creates a copy of $H$. The saturation number, denoted $\mathrm{sat}(n,H)$, is the minimum number of edges in an $H$-saturated graph on $n$ vertices. The graph saturation problem is the problem of determining $\mathrm{sat}(n,H)$ for all graphs $H$ and positive integers $n$.

The saturation number was introduced in 1964 by Erdős, Hajnal, and Moon as a dual to the extremal number $\mathrm{ex}(n,H)$. The extremal number $\mathrm{ex}(n,H)$ is the maximum number of edges in an $H$-saturated graph on $n$ vertices; this is equivalent to its original definition as the maximum number of edges in an $n$-vertex graph with no copy of $H$.

Results

Trivially, all complete bipartite graphs (with at least three edges) are [[cycle graph|Template:Mvar]]-saturated, and more generally, all [[multipartite|Template:Mvar-partite graphs]] (with at least $k+1$ edges) are Template:Mvar-saturated.

Complete graphs

The following theorem exactly determines the saturation number for complete graphs.

Theorem (Erdős, Hajnal, and Moon, 1964). For integers $n,r$ satisfying $2\le r\le n$, $\mathrm{sat}(n,K_r)=(r-2)(n-r+2)+(\genfrac{}{}{0ex}{}{r-2}{2})$, and the unique $K_r$-saturated graph on $n$ vertices and $\mathrm{sat}(n,K_r)$ edges is the graph join of $K_{r-2}$ and the empty graph ${\bar{K}}_{n-r+2}$.

General bounds

It follows from the definitions that $\mathrm{sat}(n,H)\le \mathrm{ex}(n,H)$. In contrast to the extremal number, however, for a fixed graph $H$, the saturation number $\mathrm{sat}(n,H)$ is always at most linear in $n$.

Theorem (Kászonyi and Tuza, 1986). For any fixed graph $H$, if $H$ has an isolated edge, then $\mathrm{sat}(n,H)=c_H+o(1)$ for some constant $c_H$, and otherwise, $\mathrm{sat}(n,H)=\mathrm{\Theta }(n)$. In particular, $\mathrm{sat}(n,H)=O(n)$.

It is conjectured that a stronger form of asymptotic stability holds.

Conjecture (Tuza, 1986). For any graph $H$, $\underset{n\to \mathrm{\infty }}{lim}\frac{\mathrm{sat}(n,H)}{n}$ exists.

A survey by Currie, J. Faudree, R. Faudree, and Schmitt describes progress on the graph saturation problem and related problems.