Discrete Mathematics and Combinatorics Commons^™

Extremal Problems In Graph Saturation And Covering, Adam Volk

Department of Mathematics: Dissertations, Theses, and Student Research

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 …