
arXiv: 1112.1923
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 ${\rm 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 ${\rm indsat}(n,P_4)=\lceil (n+1)/3\rceil$ for $n\geq 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.
14 pages, 7 figures
Extremal problems in graph theory, Boolean formulas, 05C35 (Primary) 68R10 (Secondary), saturation, trigraphs, induced subgraphs, Saturation, Induced subgraphs, Theoretical Computer Science, Trigraphs, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO)
Extremal problems in graph theory, Boolean formulas, 05C35 (Primary) 68R10 (Secondary), saturation, trigraphs, induced subgraphs, Saturation, Induced subgraphs, Theoretical Computer Science, Trigraphs, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 7 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
