Trees with at least 6ℓ+11 vertices are ℓ-reconstructible

2023/07/19 by Alexandr Kostochka, Mina Nahvi, Kostochka, Alexandr V. +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2307.10035

openalex publication_date 2023/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The (n-ℓ)-deck of an n-vertex graph is the multiset of (unlabeled) subgraphs obtained from it by deleting ℓ vertices. An n-vertex graph is ℓ-reconstructible if it is determined by its (n-ℓ)-deck, meaning that no other graph has the same deck. We prove that every tree with at least 6ℓ+11 vertices is ℓ-reconstructible.

Related

• Reconstruction from smaller cards
• Acyclic graphs with at least 2ℓ+1 vertices are ℓ-recognizable
• Acyclic graphs with at least 2ℓ+1 vertices are ℓ-recognizable
• Caterpillars with n vertices are reconstructible from subgraphs with at most n/2+1 vertices
• Degree lists and connectedness are 3-reconstructible for graphs with at least seven vertices