Induced Saturation Number

Abstract

In this paper, we discuss a generalization of the notion of saturation in graphs in order to deal with induced structures. In particular, we define $\mathrm{indsat}(n,H)$, which is the fewest number of gray edges in a trigraph so that no realization of that trigraph has an induced copy of $H$, but changing any white or black edge to gray results in some realization that does have an induced copy of $H$. We give some general and basic results and then prove that $\mathrm{indsat}(n,P_4)=\lceil (n+1)/3\rceil$ for $n\ge 4$ where $P_4$ is the path on 4 vertices. We also show how induced saturation in this setting extends to a natural notion of saturation in the context of general Boolean formulas.

arXiv comment14 pages, 7 figures

Cited by in corpus (5)

• Induced Saturation of Graphs
• Induced Saturation of $P_6$
• On induced saturation for paths
• Generalized saturation problems for cliques, paths, and stars
• $P_n$-induced-saturated graphs exist for all $n\ge 6$