Faudree, Jill R.; Faudree, Ralph J.; Schmitt, John R.

A survey of minimum saturated graphs

Electron. J. Comb. DS19, 36 p., electronic only (2011)


Summary: Given a family of (hyper)graphs F a (hyper)graph G is said to be F-saturated if G is F -free for any F $\in F$ but for any edge e in the complement of G the (hyper)graph G + e contains some F $\in F$. We survey the problem of determining the minimum size of an F-saturated (hyper)graph and collect many open problems and conjectures.

Mathematics Subject Classification