The edge spectrum of $K_4^{-}$-saturated graphs

Abstract

Given graphs $G$ and $H$, $G$ is $H$-saturated if $G$ does not contain a copy of $H$ but the addition of any edge $e\notin E(G)$ creates at least one copy of $H$ within $G$. The edge spectrum of $H$ is the set of all possible sizes of an $H$-saturated graph on $n$ vertices. Let $K_4^{-}$ be a graph obtained from $K_4$ by deleting an edge. In this note, we show that (a) if $G$ is a $K_4^{-}$-saturated graph with $|V(G)|=n$ and $|E(G)|>\lfloor \frac{n-1}{2}\rfloor \lceil \frac{n-1}{2}\rceil +2$, then $G$ must be a bipartite graph; (b) there exists a $K_4^{-}$-saturated non-bipartite graph on $n\ge 10$ vertices with size being in the interval $\left[3n-11,\lfloor \frac{n-1}{2}\rfloor \lceil \frac{n-1}{2}\rceil +2\right]$. Together with a result of Fuller and Gould in [{\it On ($K_t-e$)-Saturated Graphs. Graphs Combin., 2018}], we determine the edge spectrum of $K_4^{-}$ completely, and a conjecture proposed by Fuller and Gould in the same paper also has been resolved.

5 pages