On the class reconstruction number of trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913309742071808 |
|---|---|
| author | Krasikov, Ilia Roditty, Yehuda Thatte, Bhalchandra D. |
| author_facet | Krasikov, Ilia Roditty, Yehuda Thatte, Bhalchandra D. |
| contents | Harary and Lauri conjectured that the class reconstruction number of trees is 2, that is, each tree has two unlabelled vertex-deleted subtrees that are not both in the deck of any other tree. We show that each tree $T$ can be reconstructed up to isomorphism given two of its unlabelled subgraphs $T-u$ and $T-v$ under the assumption that $u$ and $v$ are chosen in a particular way. Our result does not completely resolve the conjecture of Harary and Lauri since the special property defining $u$ and $v$ cannot be recognised from the given subtrees $T-u$ and $T-v$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_17026 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the class reconstruction number of trees Krasikov, Ilia Roditty, Yehuda Thatte, Bhalchandra D. Combinatorics 05C60 Harary and Lauri conjectured that the class reconstruction number of trees is 2, that is, each tree has two unlabelled vertex-deleted subtrees that are not both in the deck of any other tree. We show that each tree $T$ can be reconstructed up to isomorphism given two of its unlabelled subgraphs $T-u$ and $T-v$ under the assumption that $u$ and $v$ are chosen in a particular way. Our result does not completely resolve the conjecture of Harary and Lauri since the special property defining $u$ and $v$ cannot be recognised from the given subtrees $T-u$ and $T-v$. |
| title | On the class reconstruction number of trees |
| topic | Combinatorics 05C60 |
| url | https://arxiv.org/abs/2312.17026 |