Derrick Stolee - Iowa State University - Research Browser

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
Software
Data
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
Uniquely $K_r$-saturated graphs, AMS Special Session on ??? AMS-MAA Joint Math Meetings, Boston, MA, January 6, 2012.
Slides Paper
Searching for uniquely $K_r$-saturated graphs using coupled augmentations, Discrete Math Seminar Iowa State University, October 11, 2011.
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

Derrick Stolee - Iowa State University - Research Browser