Nýdl's reconstructibility conjecture for trees
Nýdl's reconstructibility conjecture for trees
For an -vertex graph, the -deck is the multiset of its unlabeled induced -vertex subgraphs, and a family of graphs is weakly -reconstructible if no two graphs in the family have the same -deck. Nýdl's conjecture. For , no two -vertex trees have the same -deck; equivalently, trees with at least vertices are weakly -reconstructible. The conjecture is refuted by two -vertex trees with the same -deck, although the stated bound is sharp in general because examples with vertices and the same -deck are known.
Sources & referencesView supporting material
Primary source
Alexandr V. Kostochka, Zishen Qu, Maddy Ritter and Douglas B. West, “Caterpillars with n vertices are reconstructible from subgraphs with at most n/2+1 vertices”, arXiv:2511.23309 (2025).
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.