Universal Vertices and Saturation Numbers for Disjoint Triangles

Abstract

A graph $G$ is $\mathcal{F}$-saturated if $G$ contains no member of $\mathcal{F}$, but the addition of any non-edge creates a copy of a member of $\mathcal{F}$. For $m\ge 1$, let $(m+1)K_3$ denote the vertex-disjoint union of $(m+1)$ triangles. In this paper, we study $(m+1)K_3$-saturated graphs. We construct a family of $(m+1)K_3$-saturated graphs which gives the uniform upper bound $\mathrm{sat}((m+1)K_3,n)=O(n^{3/2})$ for all $m\ge 1$ and $n\ge 3m+3$. For general $(m+1)K_p$-saturated graphs, Faudree et al. determined $\mathrm{sat}((m+1)K_p,n)$ for sufficiently large $n$. In the case of $p=3$, we lower Faudree's threshold from $n\ge 12m+3$ to $n\ge 9m+5$ and prove that $\mathrm{sat}((m+1)K_3,n)=n+6m-1.$ We also provide two structural restrictions on the components obtained after deleting all vertices of degree $|V(G)|-1$ from an $(m+1)K_3$-saturated graph.