Delphi.science

Asymmetric induced saturation

Xinyue Fan, Sahab Hajebi, Sepehr Hajebi, Sophie Spirkl

arXivarxiv/2606.24763Jun 23, 2026math.COscore 0

For which graphs $H$ does there exist a graph $G$ with at least one edge and no induced subgraph isomorphic to $H$, such that deleting any edge of $G$ creates an induced copy of $H$? We call such a graph "$H$-deletion-saturated". This version of the well-studied notion of "$H$-induced-saturated" graphs -- where both adding and deleting any edge creates an induced copy of $H$ -- appears more tractable. For example, while it remains wide open whether $H$-induced-saturated graphs exist for every even cycle $H$, we proved recently that deletion-saturated graphs exist for all even cycles. In…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2606.24763
curl -X POST /api/v1/records/arxiv/2606.24763/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.24763/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'