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: | Text |
| Language: | unknown |
| Published: |
2021
|
| Subjects: | |
| Online Access: | http://arxiv.org/abs/2112.01094 |
| id |
ftarxivpreprints:oai:arXiv.org:2112.01094 |
|---|---|
| record_format |
openpolar |
| spelling |
ftarxivpreprints:oai:arXiv.org:2112.01094 2023-09-05T13:19:58+02:00 Optimally reconstructing caterpillars Hunter, Zach 2021-12-02 http://arxiv.org/abs/2112.01094 unknown http://arxiv.org/abs/2112.01094 Mathematics - Combinatorics text 2021 ftarxivpreprints 2023-08-16T16:49:00Z 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. Comment: 20 pages, comments welcome! (fixed typos on pages 1, 7, 9, 10 and the bibliography) Text Groenland ArXiv.org (Cornell University Library) |
| institution |
Open Polar |
| collection |
ArXiv.org (Cornell University Library) |
| op_collection_id |
ftarxivpreprints |
| language |
unknown |
| topic |
Mathematics - Combinatorics |
| spellingShingle |
Mathematics - Combinatorics Hunter, Zach Optimally reconstructing caterpillars |
| topic_facet |
Mathematics - Combinatorics |
| description |
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. Comment: 20 pages, comments welcome! (fixed typos on pages 1, 7, 9, 10 and the bibliography) |
| format |
Text |
| author |
Hunter, Zach |
| author_facet |
Hunter, Zach |
| author_sort |
Hunter, Zach |
| title |
Optimally reconstructing caterpillars |
| title_short |
Optimally reconstructing caterpillars |
| title_full |
Optimally reconstructing caterpillars |
| title_fullStr |
Optimally reconstructing caterpillars |
| title_full_unstemmed |
Optimally reconstructing caterpillars |
| title_sort |
optimally reconstructing caterpillars |
| publishDate |
2021 |
| url |
http://arxiv.org/abs/2112.01094 |
| genre |
Groenland |
| genre_facet |
Groenland |
| op_relation |
http://arxiv.org/abs/2112.01094 |
| _version_ |
1776200730649034752 |