Saturation in Graphs (Spring 2027)


A graph (G) consists of a set of vertices (V(G)) and a set of edges (E(G)), where each edge connects two vertices. How close can a graph come to containing a particular pattern without actually containing it?


Let (H) be a fixed graph. We say that (G) is (H)-saturated if (G) does not contain a copy of (H), but adding any missing edge to (G) creates a copy of (H). The saturation number (sat(G, H)) is the minimum number of edges in an (H)-saturated subgraph of (G). Saturation problems ask how few edges a graph can have while still being as close as possible to containing a forbidden configuration.


In this project, we will investigate saturation numbers for different choices of the host graph (G) and the forbidden graph (H). We will begin by considering familiar graphs such as paths, cycles, complete graphs, grids, and hypercubes, and try to determine or estimate their saturation numbers. Of particular interest will be the hypercube (Q_n), whose vertices are the binary strings of length (n), with two vertices adjacent when they differ in exactly one coordinate. In particular, we will investigate (sat(Q_n,H)), the minimum number of edges in an (H)-saturated subgraph of the (n)-dimensional hypercube, for several choices of (H), including even cycles and trees. The goal will be to discover interesting constructions, formulate conjectures, and prove exact results or general bounds where possible.


For more information contact Ramon Garcia (rgarcia2@iastate.edu)

People:

Pre-requisites: