DOI: 10.1002/jgt.23027 ISSN:
Acyclic graphs with at least 2ℓ + 1 vertices are ℓ‐recognizable
Alexandr V. Kostochka, Mina Nahvi, Douglas B. West, Dara Zirlin- Geometry and Topology
- Discrete Mathematics and Combinatorics
Abstract
The ‐deck of an ‐vertex graph is the multiset of subgraphs obtained from it by deleting vertices. A family of ‐vertex graphs is ‐recognizable if every graph having the same ‐deck as a graph in the family is also in the family. We prove that the family of ‐vertex graphs with no cycles is ‐recognizable when (except for ). As a consequence, the family of ‐vertex trees is ‐recognizable when and . It is known that this fails when .