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]

References

1. Currie, Bryan L.; Faudree, Jill R.; Faudree, Ralph J.; Schmitt, John R. (2021). "A Survey of Minimum Saturated Graphs". The Electronic Journal of Combinatorics. 2. DS19. doi:10.37236/41.
2. Erdős, P.; Hajnal, A.; Moon, J. W. (1964). "A Problem in Graph Theory". The American Mathematical Monthly. 71 (10): 1107–1110. doi:10.2307/2311408.
3. Kászonyi, L.; Tuza, Zs. (June 1986). "Saturated graphs with minimal number of edges". Journal of Graph Theory. 10 (2): 203–210. doi:10.1002/jgt.3190100209.
4. Tuza, Zs. (1986). "A generalization of saturated graphs for finite languages". Proceedings of the 4th international meeting of young computer scientists, IMYCS ’86 (Smolenice Castle, 1986). Tanulmányok. MTA Számitástechnikai és Automatizálási Kutató Intézet Budapest. No. 185. pp. 287–293.
5. Tuza, Zsolt (1988). Extremal problems on saturated graphs and hypergraphs. Eleventh British Combinatorial Conference (London, 1987). Ars Combinatoria. Vol. 25. pp. 105–113.