Back to search

University of Waterloo

On Induced Saturation in Graphs and Tournaments

Abstract

dc:description.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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Fan, Xinyue

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/23134

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Fan, Xinyue. On Induced Saturation in Graphs and Tournaments. University of Waterloo, 2026. https://hdl.handle.net/10012/23134