The Edge Spectrum of $K_4$-Saturated Graphs

Abstract

Any $H$-free graph $G$ is called $H$-saturated if the addition of any edge $e\notin E(G)$ results in $H$ as a subgraph of $G$. The minimum size of an $H$-saturated graph on $n$ vertices is denoted by $sat(n,H)$. The edge spectrum for the family of graphs with property $P$ is the set of all sizes of graphs with property $P$. In this paper, we find the edge spectrum of $K_4$-saturated graphs. We also show that if $G$ is a $K_4$-saturated graph, then either $G\cong K_{1,1,n-2}$ or $\delta (G)\ge 3$, and we detail the exact structure of a $K_4$-saturated graph with $\kappa (G)=2$ and $\kappa (G)=3$.