On the class reconstruction number of trees
| Autor: | Krasikov, Ilia, Roditty, Yehuda, Thatte, Bhalchandra D. |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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$. Comment: 5 pages, 2 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|