Kelly's reconstruction conjecture for graphs
Kelly's reconstruction conjecture for graphs
Let be a graph on vertices. For each vertex , let be the subgraph obtained by deleting from , and let
be the multiset of all vertex-deleted subgraphs, called the deck. Kelly's reconstruction conjecture. Any two graphs and on vertices with equal multisets and are isomorphic. This is a classical open problem in graph theory: it asks whether a graph is determined up to isomorphism by its vertex-deleted subgraphs, although important special cases are known.
Sources & referencesView supporting material
Primary source
David Hartman, Aneta Pokorná, Daniel Trlifaj and Lluís Vena, “Reconstructing graphs and their connectivity using graphlets”, arXiv:2508.19189 (2025).
Additional references
3 papers in this index state this conjecture (2014–2025). The statement above is taken from the most recent of them; the others are arXiv:1808.10034, arXiv:1406.7870.
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.