Odd Covers and Graph Saturation

The purpose of this dissertation is twofold: to introduce a unifying framework for what we call odd cover problems and to provide new insight into graph saturation. An odd cover of a graph G is a collection of graphs such that every edge of G occurs in an odd number, and every nonedge in an even number, of graphs in the collection. We direct our interest towards finding the minimum cardinality of an odd cover of G with graphs from specific classes, in the vein of partitioning results like the Graham-Pollak theorem. Mainly, we focus on the classes of cliques and bicliques, but we also note results on odd covers with tricliques, paths (relating to Gallai's conjecture), and cycles. We find this value for various graphs G in each setting, including for all odd (and some even) cliques in the setting of bicliques, marking significant progress on a 1988 problem of Babai and Frankl. Deep relations to linear algebra are demonstrated: the minimum cardinality of an odd cover of a graph with cliques is either equal to or one more than its minimum rank over the binary field; and the minimum cardinality of an odd cover of a graph with bicliques is bounded above by the binary rank of its adjacency matrix and below by half this rank. In Part II, we turn our attention to more extremal problems. The saturation number of a graph H is the minimum number of edges in an n-vertex graph which does not contain H as a subgraph, but to which the addition of any extra edge creates a copy of H. Saturation numbers of cliques were determined in 1964 by Erdős, Hajnal, and Moon, complementing one of the earliest extremal results: Turán's theorem. We prove a general lower bound on the saturation number and use it to determine the saturation numbers of unbalanced double stars asymptotically, resolving the last open cases of asymptotic saturation numbers of trees with diameter at most 3. We also provide upper bounds on the saturation numbers of certain trees of larger diameter, called caterpillars. Finally, we examine an edge-colored version of saturation, analogous to the rainbow Turán number, proving bounds on the (proper) rainbow saturation numbers of double stars.