Uniquely $K_r$-saturated graphs

Problem and Results Summary

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.

Research Papers

S. G. Hartke, D. Stolee,
Uniquely $K_r$-saturated graphs,
*Electronic Journal of Combinatorics*
**19**(4), P6, 40 pages.

Web Version ArXiv Version Official Version

Web Version ArXiv Version Official Version

Software

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

Data

- Graphs in graph6 and adjacency matrix forms.

Support

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

Related Work

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).

Presentations

Computational Combinatorics and the search for Uniquely Kr-Saturated Graphs. *Department of Computer Science Colloquium*, Iowa State University.

Slides Research Project

Slides Research Project

Uniquely $K_r$-saturated graphs,
*AMS Special Session on ???* AMS-MAA Joint Math Meetings, Boston, MA, January 6, 2012.

Slides Paper

Slides Paper

Searching for uniquely $K_r$-saturated graphs using coupled augmentations,
*Discrete Math Seminar* Iowa State University, October 11, 2011.

Slides Paper

Slides Paper

Searching for uniquely $K_r$-saturated (and strongly regular) graphs using coupled augmentations,
*AMS Special Session on ???* AMS Southeastern Sectional Meeting, Wake Forest, NC, September ??, 2011.

Slides Paper

Slides Paper