Uniquely $K_r$-Saturated Graphs

  • Stephen G. Hartke
  • Derrick Stolee
Keywords: uniquely saturated graphs, Cayley graphs, orbital branching, computational combinatorics


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 $\mathbb{Z}_n$ with a small number of generators.

Author Biographies

Stephen G. Hartke, University of Nebraska-Lincoln
Associate Professor, Department of Mathematics
Derrick Stolee, University of Illinois

J. L. Doob Research Assistant Professor, Department of Mathematics

Article Number