Deletion-only Induced Saturation on Trees

Xinyue Fan, University of Waterloo

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. It is natural to ask: 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 tree H. In this talk, we consider a weaker variant that only concerns about removing edges, and specifically look at non-complete trees with two leaves at distance at most three where k-uniform hypergraphs play important roles in the proof. This follows from an even stronger result for graphs with two leaves satisfying certain technical conditions.

This is joint work with Sahab Hajebi, Sepehr Hajebi, and Sophie Spirkl.