A Lower Bound on the Saturation Number and a Strengthening for Triangle-Free Graphs

The saturation number 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 sat (n, H). In this paper, we present another lower bound on 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ₒ, ₓ of order s + t whose central vertices have degrees s and t. Faudree, Faudree, Gould, and Jacobson determined that sat (n, Sₓ, ₓ) = (t-1) n/2 + O (1). We prove that sat (n, Sₒ, ₓ) = (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.