Extremal Problems in Graph Saturation and Covering

This dissertation considers several problems in extremal graph theory with the aim of finding the maximum or minimum number of certain subgraph counts given local conditions. The local conditions of interest to us are saturation and covering. Given graphs F and H, a graph G is said to be F-saturated if it does not contain any copy of F, but the addition of any missing edge in G creates at least one copy of F. We say that G is H-covered if every vertex of G is contained in at least one copy of H. In the former setting, we prove results regarding the minimum number of copies of certain subgraphs, primarily cliques and stars. Special attention will be given to the somewhat surprising challenge of minimizing the number of cherries, i.e. stars with two vertices of degree 1, in triangle-saturated graphs and its connection to Moore graphs. In the latter setting, we are interested in maximizing the number of independent sets of a fixed size in H-covered graphs, primarily when H is a star, path, or disjoint union of edges. Along the way, we will introduce and prove several results regarding a new style of question regarding graph saturation, namely determining for which graphs F there exist trees that are F-saturated. We will call such graphs tree-saturating. Adviser: Jamie Radcliff