Saturation (graph theory)
In 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 are [cycle graph|]-saturated, and more generally, all -partite graphs are -saturated.Complete graphs
The following theorem exactly determines the saturation number for complete graphs.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.It is conjectured that a stronger form of asymptotic stability holds.
A survey by Currie, J. Faudree, R. Faudree, and Schmitt describes progress on the graph saturation problem and related problems.