2023/08/08 by Alexandr Kostochka, Mina Nahvi, Kostochka, Alexandr V. +5
Computer Science · Mathematics · #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2308.04509
The (n-ℓ)-deck of an n-vertex graph is the multiset of subgraphs obtained from it by deleting ℓ vertices. A family of n-vertex graphs is ℓ-recognizable if every graph having the same (n-ℓ)-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 ℓ-recognizable when n≥2ℓ+1 (except for (n,ℓ)=(5,2)). As a consequence, the family of n-vertex trees is ℓ-recognizable when n≥2ℓ+1 and ℓ≠2. It is known that this fails when n=2ℓ.