| Autor: |
Kostochka, Alexandr V., Nahvi, Mina, West, Douglas B., Zirlin, Dara |
| Rok vydání: |
2023 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
The $(n-\ell)$-deck of an $n$-vertex graph is the multiset of subgraphs obtained from it by deleting $\ell$ vertices. A family of $n$-vertex graphs is $\ell$-recognizable if every graph having the same $(n-\ell)$-deck as a graph in the family is also in the family. We prove that the family of $n$-vertex graphs with no cycles is $\ell$-recognizable when $n\ge2\ell+1$ (except for $(n,\ell)=(5,2)$). As a consequence, the family of $n$-vertex trees is $\ell$-recognizable when $n\ge2\ell+1$ and $\ell\ne2$. It is known that this fails when $n=2\ell$. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
