Caterpillars with $n$ vertices are reconstructible from subgraphs with at most $n/2+1$ vertices

Abstract

The $\textit{$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\ge 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\ge 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.

60 pages, 4 figures