Manvel's bounded-deletion reconstruction conjecture for graphs
Manvel's bounded-deletion reconstruction conjecture for graphs
Let . A graph is -reconstructible if its isomorphism type is determined by its -deck, the multiset of induced subgraphs obtained by deleting vertices from an -vertex graph.
Manvel's conjecture. For each , there exists a threshold such that every graph with at least vertices is -reconstructible.
This extends the classical Reconstruction Conjecture to deletion of an arbitrary fixed number of vertices. The source does not give a resolution of this conjecture.
Sources & referencesView supporting material
Primary source
Alexandr V. Kostochka, Mina Nahvi, Douglas B. West and Dara Zirlin, “Acyclic graphs with at least 2+1 vertices are -recognizable”, arXiv:2308.04509 (2023).
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.