Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.23309 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917112249843712 |
|---|---|
| author | Kostochka, Alexandr V. Qu, Zishen Ritter, Maddy West, Douglas B. |
| author_facet | Kostochka, Alexandr V. Qu, Zishen Ritter, Maddy West, Douglas B. |
| contents | 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\ge48$ 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\ge6$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_23309 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Caterpillars with $n$ vertices are reconstructible from subgraphs with at most $n/2+1$ vertices Kostochka, Alexandr V. Qu, Zishen Ritter, Maddy West, Douglas B. Combinatorics 05C60 (Primary), 05C05 (Secondary) 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\ge48$ 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\ge6$ 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. |
| title | Caterpillars with $n$ vertices are reconstructible from subgraphs with at most $n/2+1$ vertices |
| topic | Combinatorics 05C60 (Primary), 05C05 (Secondary) |
| url | https://arxiv.org/abs/2511.23309 |