Saturated Graphs of Prescribed Minimum Degree

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)$ and discuss an analogous problem for saturated hypergraphs.

15 pages