ABSTRACT

This chapter focuses on developments of the saturated graphs. A natural dual of extremal numbers was introduced by A. Zykov, and independently by P. Erdos, A. Hajnal, and J. Moon. Instead of asking for the maximum number of edges in an H-saturated graph on n vertices, they wanted the minimum such number. There are a number of results that are important to the development of saturation numbers. One type of tree plays an important role. A perfect degree three tree is a tree such that each vertex has degree 3 or 1, and all vertices of degree 1 are the same distance from the center of the tree. These trees are also called complete 1, 3-trees. A linear forest is a disjoint union of paths. In a number of results and conjectures on saturation numbers for linear forests were presented.