Journal of Combinatorics

Volume 1 (2010)

Number 2

The saturation function of complete partite graphs

Pages: 149 – 170

DOI: http://dx.doi.org/10.4310/JOC.2010.v1.n2.a5

Authors

Tom Bohman (Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Penn., U.S.A.)

Maria Fonoberova (Aimdyn, Inc., Santa Barbara, Calif., U.S.A.)

Oleg Pikhurko (Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Penn., U.S.A.)

Abstract

A graph $G$ is called \emph{$F$-saturated} if it is $F$-free but theaddition of any missing edge to $G$ creates a copy of $F$.Let the saturation function $\sat(n,F)$ be the minimum numberof edges that an $F$-saturated graph on $n$ vertices can have.We determine this function asymptotically forevery fixed complete partite graph $F$ as $n$ tends to infinity andgive some structural information aboutalmost 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.

Full Text (PDF format)