A lower bound on the saturation number, and graphs for which it is sharp
share
Let H be a fixed graph. We say that a graph G is H-saturated if it has no subgraph isomorphic to H, but the addition of any edge to G results in an H-subgraph. The saturation number sat(H,n) is the minimum number of edges in an H-saturated graph on n vertices. Kászonyi and Tuza, in 1986, gave a general upper bound on the saturation number of a graph H, but a nontrivial lower bound has remained elusive. In this paper we give a general lower bound on sat(H,n) and prove that it is asymptotically sharp (up to an additive constant) on a large class of graphs. This class includes all threshold graphs and many graphs for which the saturation number was previously determined exactly. Our work thus gives an asymptotic common generalization of several earlier results. The class also includes disjoint unions of cliques, allowing us to address an open problem of Faudree, Ferrara, Gould, and Jacobson.
READ FULL TEXT