Manvel's bounded-deletion reconstruction conjecture for graphs

Let N\ell\in\mathbb{N}. A graph is \ell-reconstructible if its isomorphism type is determined by its (n)(n-\ell)-deck, the multiset of induced subgraphs obtained by deleting \ell vertices from an nn-vertex graph.

Manvel's conjecture. For each N\ell\in\mathbb{N}, there exists a threshold MM_\ell such that every graph with at least MM_\ell vertices is \ell-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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.