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 ${\displaystyle H}$, a graph ${\displaystyle G}$ is said to be ${\displaystyle H}$-saturated if ${\displaystyle G}$ does not contain a copy of ${\displaystyle H}$ as a subgraph, but adding any edge to ${\displaystyle G}$ creates a copy of ${\displaystyle H}$. The saturation number, denoted ${\displaystyle \operatorname {sat} (n,H)}$, is the minimum number of edges in an ${\displaystyle H}$-saturated graph on ${\displaystyle n}$ vertices. The graph saturation problem is the problem of determining ${\displaystyle \operatorname {sat} (n,H)}$ for all graphs ${\displaystyle H}$ and positive integers ${\displaystyle n}$.^[1]

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

Results

Complete graphs

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

Theorem (Erdős, Hajnal, and Moon, 1964). For integers ${\displaystyle n,r}$ satisfying ${\displaystyle 2\leq r\leq n}$, ${\textstyle \operatorname {sat} (n,K_{r})=(r-2)(n-r+2)+{\binom {r-2}{2}}}$, and the unique ${\displaystyle K_{r}}$-saturated graph on ${\displaystyle n}$ vertices and ${\displaystyle \operatorname {sat} (n,K_{r})}$ edges is the graph join of ${\displaystyle K_{r-2}}$ and the empty graph ${\displaystyle {\overline {K}}_{n-r+2}}$.^[2]

General bounds

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

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

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

Conjecture (Tuza, 1986). For any graph ${\displaystyle H}$, ${\textstyle \lim _{n\to \infty }{\frac {\operatorname {sat} (n,H)}{n}}}$ exists.^[4][5]

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