Saturation (graph theory)

This article is about the problem in extremal graph theory. For the definition in matching theory, see Glossary of graph theory § 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 $\operatorname {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 $\operatorname {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 $\operatorname {ex} (n,H)$. The extremal number $\operatorname {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

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\leq r\leq n$, ${\textstyle \operatorname {sat} (n,K_{r})=(r-2)(n-r+2)+{\binom {r-2}{2}}}$, and the unique $K_{r}$-saturated graph on $n$ vertices and $\operatorname {sat} (n,K_{r})$ edges is the graph join of $K_{r-2}$ and the empty graph ${\overline {K}}_{n-r+2}$.

General bounds

It follows from the definitions that $\operatorname {sat} (n,H)\leq \operatorname {ex} (n,H)$. In contrast to the extremal number, however, for a fixed graph $H$, the saturation number $\operatorname {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 $\operatorname {sat} (n,H)=c_{H}+o(1)$ for some constant $c_{H}$, and otherwise, $\operatorname {sat} (n,H)=\Theta (n)$. In particular, $\operatorname {sat} (n,H)=O(n)$.

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

Conjecture (Tuza, 1986). For any graph $H$, ${\textstyle \lim _{n\to \infty }{\frac {\operatorname {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.