Uniquely $C_4^{+}$-saturated graphs

Abstract

A graph $G$ is uniquely $H$-saturated if it contains no copy of a graph $H$ as a subgraph, but adding any new edge into $G$ creates exactly one copy of $H$. Let $C_4^{+}$ be the diamond graph consisting of a $4$-cycle $C_4$ with one chord and $C_3^{\ast }$ be the graph consisting of a triangle with a pendant edge. In this paper we prove that a nontrivial uniquely $C_4^{+}$-saturated graph $G$ has girth $3$ or $4$. Further, $G$ has girth $4$ if and only if it is a strongly regular graph with special parameters. For $n>18k^2-24k+10$ with $k\ge 2$, there are no uniquely $C_4^{+}$-saturated graphs on $n$ vertices with $k$ triangles. In particular, $C_3^{\ast }$ is the only nontrivial uniquely $C_4^{+}$-saturated graph with one triangle, and there are no uniquely $C_4^{+}$-saturated graphs with two, three or four triangles.

14 pages, 2 figures