The saturation number of W 4

Abstract

For a fixed graph $H$, a graph $G$ is called $H$-saturated if $G$ does not contain $H$ as a (not necessarily induced) subgraph, but $G+e$ contains a copy of $H$ for any $e\in E(\overline{G})$. The saturation number of $H$, denoted by $\mathrm{sat}(n,H)$, is the minimum number of edges in an $n$-vertex $H$-saturated graph. A wheel $W_n$ is a graph obtained from a cycle of length $n$ by adding a new vertex and joining it to every vertex of the cycle. A well-known result of Erdős, Hajnal and Moon shows that $\mathrm{sat}(n,W_3)=2n-3$ for all $n\ge 4$ and $K_2\vee \overline{K_{n-2}}$ is the unique extremal graph, where $\vee$ denotes the graph join operation. In this paper, we study the saturation number of $W_4$. We prove that $\mathrm{sat}(n,W_4)=\lfloor \frac{5n-10}{2}\rfloor$ for all $n\ge 6$ and give a complete characterization of the extremal graphs.

36pages, 9 figures