A Survey of Minimum Saturated Graphs

By J. Faudree, R. Faudree, John R. Schmitt. 2011

194 citations recorded by the source corpus.

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

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/1582d81e254f0fd01c53079f078349d0d4397530