2025/11/28 by Kostochka, Alexandr V., Qu, Zishen, Ritter, Maddy +1
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Digital Image Processing Techniques #Advanced Graph Theory Research
paper · doi:10.48550/arxiv.2511.23309
The m-deck of an n-vertex graph is the multiset of unlabeled induced subgraphs with m vertices. Caterpillars are trees in which all nonleaf vertices lie on a single path. We prove for n≥48 that any n-vertex caterpillar is reconstructible (up to isomorphism) from its m-deck when m>n/2. The result is sharp, since for n≥6 there are two n-vertex caterpillars having the same \lfloor n/2 \rfloor-deck. Our result proves the special case for caterpillars of a 1990 conjecture by Nýdl about trees.