Computational Combinatorics: Uniquely $K_r$-saturated Graphs

We discuss an experimental mathematics approach to discrete mathematics, using the example of uniquely $K_r$-saturated graphs as a case study. A graph $G$ is uniquely $K_r$-saturated if it contains no clique with $r$ vertices and if for all edges $e$ in the complement, $G+e$ has a unique clique with $r$ vertices. Previously, few examples of uniquely $K_r$-saturated graphs were known, and little was known about their properties. We search for these graphs by adapting orbital branching, a technique originally developed for symmetric integer linear programs. We find several new uniquely $K_r$-saturated graphs with $4 \leq r \leq 7$, as well as two new infinite families based on Cayley graphs for $Z_n$ with a small number of generators. This talk is based on joint work with Derrick Stolee.

Speaker Bio: Stephen Hartke obtained a B.S. in Mathematics and Computer Science from the University of Dayton in Ohio and received his Ph.D. in Mathematics from Rutgers University in New Jersey. He was an NSF VIGRE Research Assistant Professor at the University of Illinois at Urbana-Champaign and is currently an Associate Professor at the University of Nebraska-Lincoln. Hartke is interested in developing computational approaches to problems in discrete mathematics and in particular graph theory.

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.