Saturation Numbers
by
Ralph Faudree
University of Memphis

A graph G is an H-saturated graph if G does not contain H as a subgraph, but G ∪{e} contains a copy of H for any edge not in G. The saturation number of H, denoted by sat(H, n), is the minimum number of edges in an H-saturated graph G of order n. A survey of some of the classical results on saturation numbers will be presented, also with a comparison of the saturation number sat(H, n) with the Turán extremal number ex(H, n). However, the focus will be on some recent results on saturation numbers. This will include saturation numbers for disjoint union of complete graphs, generalized fans, books and generalized books, and special classes of trees.

Date received: March 11, 2008