The $ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $ell$ vertices. In 1976, Giles proved that any tree on $ngeq 6$ vertices can be reconstructed from its $ell$-deck for $ell geq n-2$. Our main theorem states that it is enough to have $ellgeq (8/9+o(1))n$, making substantial progress towards a conjecture of Nydl from 1990. In addition, we can recognise connectedness from the $ell$-deck if $ellgeq 9n/10$, and reconstruct the degree sequence from the $ell$-deck if $ellge sqrt{2nlog(2n)}$. All of these results are significant improvements on previous bounds.
تحميل البحث