Uniquely cycle-saturated graphs
classification
🧮 math.CO
keywords
uniquelysaturatedgraphsgraphthereonlyaddingcomplement
read the original abstract
Given a graph $F$, a graph $G$ is {\it 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 paper we study uniquely $C_t$-saturated graphs. We prove the following: (1) a graph is uniquely $C_5$-saturated if and only if it is a friendship graph. (2) There are no uniquely $C_6$-saturated graphs or uniquely $C_7$-saturated graphs. (3) For $t\ge6$, there are only finitely many uniquely $C_t$-saturated graphs (we conjecture that in fact there are none).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.