Uniquely Cycle‐Saturated Graphs
Paul S. Wenger, Douglas B. West · Journal of Graph Theory · 2016
Abstract Given a graph F, a graph G is uniquely F‐saturated if F is not a subgraph of G and adding any edge of the complement to G completes exactly one copy of F. In this article, we study uniquely ‐saturated graphs. We prove the following: (1) a graph is uniquely C5‐saturated if and only if it is a friendship graph. (2) There are no uniquely C6‐saturated graphs or uniquely C7‐saturated graphs. (3) For , there are only finitely many uniquely ‐saturated graphs (we conjecture that in fact there are none). Additionally, our results show that there are finitely many k‐friendship graphs (as defined by Kotzig) for .