Optimally reconstructing caterpillars
For a graph $G$, the $\ell$-deck of $G$ is the multiset of induced subgraphs on $G$ having $\ell$ vertices. Recently, Groenland et al. proved that any tree can be reconstructed from its $(8/9+o(1))n$-deck. For the particular case of caterpillar graphs, we show that the $(1/2+o(1))n$-deck suffices, w...
| Main Author: | |
|---|---|
| Format: | Article in Journal/Newspaper |
| Language: | unknown |
| Published: |
arXiv
2021
|
| Subjects: | |
| Online Access: | https://dx.doi.org/10.48550/arxiv.2112.01094 https://arxiv.org/abs/2112.01094 |
| Summary: | For a graph $G$, the $\ell$-deck of $G$ is the multiset of induced subgraphs on $G$ having $\ell$ vertices. Recently, Groenland et al. proved that any tree can be reconstructed from its $(8/9+o(1))n$-deck. For the particular case of caterpillar graphs, we show that the $(1/2+o(1))n$-deck suffices, which is asymptotically tight. : 20 pages, comments welcome! (fixed typos on pages 1, 7, 9, 10 and the bibliography) |
|---|