A lower bound on the saturation number and a strengthening for triangle-free graphs

Abstract

The saturation number $\mathrm{sat}(n,H)$ of a graph $H$ and positive integer $n$ is the minimum size of a graph of order $n$ which does not contain a subgraph isomorphic to $H$ but to which the addition of any edge creates such a subgraph. Erdős, Hajnal, and Moon first studied saturation numbers of complete graphs, and Cameron and Puleo introduced a general lower bound on $\mathrm{sat}(n,H)$. In this paper, we present another lower bound on $\mathrm{sat}(n,H)$ with strengthenings for graphs $H$ in several classes, all of which include the class of triangle-free graphs. Demonstrating its effectiveness, we determine the saturation numbers of diameter-$3$ trees up to an additive constant; these are double stars $S_{s,t}$ of order $s+t$ whose central vertices have degrees $s$ and $t$. Faudree, Faudree, Gould, and Jacobson determined that $\mathrm{sat}(n,S_{t,t})=(t-1)n/2+O(1)$. We prove that $\mathrm{sat}(n,S_{s,t})=(st+s)n/(2t+4)+O(1)$ when $s<t$. We also apply our lower bound to caterpillars and demonstrate an upper bound on the saturation numbers of certain diameter-$4$ caterpillars.