The saturation function of complete partite graphs

Abstract

A graph G is called F -saturated if it is F -free but the addition of any missing edge to G creates a copy of F . Let the saturation function sat(n, F ) be the minimum number of edges that an F -saturated graph on n vertices can have. We determine this function asymptotically for every fixed complete partite graph F as n tends to infinity and give some structural information about almost extremal F -saturated graphs. If the two largest parts of F have different sizes, then we can reduce the error term to an additive constant.