The reconstruction conjecture for finite simple graphs
The reconstruction conjecture for finite simple graphs
Let be a finite simple undirected graph. For each vertex , let be its card, and let
be its deck. The graph is reconstructible if every graph with is isomorphic to . The reconstruction conjecture. Every graph of order at least is reconstructible. This is one of the central open problems in structural graph theory, asserting that a graph is determined up to isomorphism by the multiset of its vertex-deleted induced subgraphs. The conjecture remains wide open, although the paper proves it for interval graphs with at least three vertices.
Sources & referencesView supporting material
Primary source
Irene Heinrich, Masashi Kiyomi, Yota Otachi and Pascal Schweitzer, “Interval Graphs are Reconstructible”, arXiv:2504.02353 (2026).
Additional references
9 papers in this index state this conjecture (2008–2025). The statement above is taken from the most recent of them; the others are arXiv:2503.20167, arXiv:2311.16665, arXiv:2210.00338, arXiv:1606.02926, arXiv:1602.02731, arXiv:1004.2375, arXiv:0810.3189, arXiv:0804.4093.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.