Acyclic graphs with at least $2\ell +1$ vertices are $\ell$-recognizable

Abstract

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 having no cycles is $\ell$-recognizable when $n\ge 2\ell +1$ (except for $(n,\ell )=(5,2)$). It is known that this fails when $n=2\ell$.

16 pages

Cited by in corpus (1)

• Optimally reconstructing caterpillars