Acyclic graphs with at least 2ℓ + 1 vertices are ℓ-recognizable

Alexandr V. Kostochka, Mina Nahvi, Douglas B. West, Dara Zirlin

Research output: Contribution to journalArticlepeer-review


The (Formula presented.) -deck of an (Formula presented.) -vertex graph is the multiset of subgraphs obtained from it by deleting (Formula presented.) vertices. A family of (Formula presented.) -vertex graphs is (Formula presented.) -recognizable if every graph having the same (Formula presented.) -deck as a graph in the family is also in the family. We prove that the family of (Formula presented.) -vertex graphs with no cycles is (Formula presented.) -recognizable when (Formula presented.) (except for (Formula presented.)). As a consequence, the family of (Formula presented.) -vertex trees is (Formula presented.) -recognizable when (Formula presented.) and (Formula presented.). It is known that this fails when (Formula presented.).

Original languageEnglish (US)
JournalJournal of Graph Theory
StateAccepted/In press - 2023


  • acyclic graph
  • deck
  • graph reconstruction
  • tree

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Acyclic graphs with at least 2ℓ + 1 vertices are ℓ-recognizable'. Together they form a unique fingerprint.

Cite this