Saturated Graphs of Prescribed Minimum Degree

Source abstract

A graph G is H -saturated if it contains no copy of H as a subgraph but the addition of any new edge to G creates a copy of H . In this paper we are interested in the function sat t ( n,p ), defined to be the minimum number of edges that a K p -saturated graph on n vertices can have if it has minimum degree at least t . We prove that sat t ( n,p ) = tn − O (1), where the limit is taken as n tends to infinity. This confirms a conjecture of Bollobás when p = 3. We also present constructions for graphs that give new upper bounds for sat t ( n,p ).