Saturation (graph theory)

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

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

Results

Trivially, all complete bipartite graphs (with at least three edges) are -saturated, and more generally, all -partite graphs (with at least edges) are -saturated.

Complete graphs

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

Theorem (Erdős, Hajnal, and Moon, 1964). For integers satisfying , , and the unique -saturated graph on vertices and edges is the graph join of and the empty graph .

General bounds

It follows from the definitions that . In contrast to the extremal number, however, for a fixed graph , the saturation number is always at most linear in .

Theorem (Kászonyi and Tuza, 1986). For any fixed graph , if has an isolated edge, then for some constant , and otherwise, . In particular, .

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

Conjecture (Tuza, 1986). For any graph , exists.

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

References