A Survey of Minimum Saturated Graphs

  • Bryan L. Currie
  • Jill R. Faudree
  • Ralph J. Faudree
  • John R. Schmitt


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


First Published
This Version
DS19: Oct 11, 2021