A graph $G$ is uniquely $H$-saturated if $G$ contains no copy of $H$ as a subgraph and for every nonedge $e \in \binom{V(G)}{2} - E(G)$ there is exactly one copy of $H$ in $G + e$. We consider the case that $H = K_r$. It is trivial to remove dominating vertices, so we focus on the interesting cases of $r$-primitive graphs which are uniquely $K_r$-saturated with no dominating vertex. The main conjecture is as follows:

Conjecture. For every $r \geq 3$, there are a finite number of $r$-primitive graphs.

This conjecture is true for $r = 3$, but the proof requires that all 3-primitive graphs are regular. In [P07], an irregular 5-primitive graph was found. Several other interesting constructions were found.

Also, two infinite families of $r$-primitive graphs (where $r$ grows with $n$) were found and proven using counting and discharging methods.

• Saturation Software, User Guide. (Requires Utilities, TreeSearch, nauty, and cliquer)

• Graphs in graph6 and adjacency matrix forms.

Research for this project was done with support by National Science Foundation Grant DMS-0914815.

J. Cooper, J. Lenz, T. D. LeSaulnier, P. S. Wenger, D. B. West, Uniquely $C_4$-saturated graphs, Graphs and Combinatorics, 28 (2012) 189-197.

Uniquely $K_r$-Saturated Graphs: Experiment #1, Computational Combinatorics (Blog).

Uniquely $K_r$-Saturated Graphs: Experiment #2, Computational Combinatorics (Blog).