This research demonstrates that for every even cycle, H, there exist H-induced-saturated graphs, suggesting new pathways for graph theory.
For graphs G and H, we say that G is H-free if no induced subgraph of G is isomorphic to H, and that G is H-induced-saturated if G is H-free but removing or adding any edge in G creates an induced copy of H. A full characterization of graphs H for which H-induced-saturated graphs exist remains elusive. Even the case where H is a path -- now settled by the collective results of Martin and Smith, Bonamy et al., and Dvo\'{r}{a}k -- was already quite challenging. What if H is a cycle? The complete answer for odd cycles was given by Behren et al., leaving the case of even cycles (except for the $4$-cycle) wide open. Our main result is the first step toward closing this gap: We prove that for every even cycle H, there is a graph G with at least one edge such that G is H-free but removing any edge from G creates an induced copy of H (in fact, we construct H-induced-saturated graphs for every even cycle H on at most 10 vertices).
No takes yet. Share an insight, caveat, or question.
Fan et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: