Reconstruction from smaller cards
Carla Groenland (TU Delft - Discrete Mathematics and Optimization)
Tom Johnston (University of Oxford)
Alex Scott (University of Oxford)
Jane Tan (University of Oxford)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The ℓ-deck of a graph G is the multiset of all induced subgraphs of G on ℓ vertices. We say that a graph is reconstructible from its ℓ-deck if no other graph has the same ℓ-deck. In 1957, Kelly showed that every tree with n ≥ 3 vertices can be reconstructed from its (n − 1)-deck, and Giles strengthened this in 1976, proving that trees on at least 6 vertices can be reconstructed from their (n − 2)-decks. Our main theorem states that trees are reconstructible from their (n − r)-decks for all r ≤ n/9 + o(n), making substantial progress towards a conjecture of Nýdl from 1990. In addition, we can recognise the connectedness of a graph from its ℓ-deck when ℓ ≥ 9n/10, and reconstruct the degree sequence when ℓ≥2nlog(2n). All of these results are significant improvements on previous bounds.
help_outline