On Induced Saturation in Graphs and Tournaments

Abstract

Let H be a graph. A graph G is H-induced-saturated if G is H-free — meaning that no induced subgraph of G is isomorphic to H — and adding or removing any edge in G leaves a graph that is no longer H-free. In this thesis, we study the following question: For which graphs H does there exist an H-induced-saturated graph G? A full answer remains out of reach; indeed, it remains open whether H-induced-saturated graphs exist for every even cycle H. This is particularly intriguing because, in contrast, Behrens et al. [1] gave a short proof that H-induced-saturated graphs exist when H is an odd cycle (except for the triangle, which is complete). A “halfway” result toward settling the case of even cycles is due to Tennenhouse [16], who showed that for every even cycle H, there exists a (non-complete) graph G that is H-free such that adding any edge to G creates an induced copy of H. Tennenhouse’s construction is remarkably simple, but it does not satisfy the edge-deletion property. Our first result complements this: We prove that for every even cycle H, there exists a (non-empty) graph G that is H-free such that deleting any edge from G creates an induced copy of H. The construction of such a graph G is rather involved, and yet unfortunately does not satisfy the edge-addition property. We also study our deletion-only relaxation of induced saturation for other choices of H. In particular, we consider the case where H is a tree, and prove that for every non-complete tree H with two leaves at distance at most three, there exists a (non-empty) graph G that is H-free such that deleting any edge of G creates an induced copy of H. In fact, we prove that every non-complete graph H with two leaves at distance at most three has this property. This follows from an even stronger result for graphs with two leaves satisfying certain technical conditions. Finally, we examine the tournament analog of induced saturation: For which tournaments H does there exist a tournament G that is H-free such that flipping the orientation of any arc of G creates a copy of H? The case where H is transitive is particularly interesting, since Ramsey’s theorem implies that only finitely many H-free tournaments exist in the first place. We prove that for every transitive tournament H, if the critical tournament exists for H, then it also exists for the tournament Δ(1, 1, H), obtained from a cyclic triangle by blowing up one vertex into a copy of H.