Reconstruction from smaller cards

Abstract: The

e l l

-deck of a graph

G

is the multiset of all induced subgraphs of

G

on

e l l

vertices. In 1976, Giles proved that any tree on

n g e q 6

vertices can be reconstructed from its

e l l

-deck for

e l l g e q n - 2

. Our main theorem states that it is enough to have

e l l g e q (8 / 9 + o (1)) n

, making substantial progress towards a conjecture of N'ydl from 1990. In addition, we can recognise connectedness from the

e l l

-deck if

e l l g e q 9 n / 10

, and reconstruct the degree sequence from the

e l l

-deck if

e l l g e s q r t 2 n l o g (2 n)

. All of these results are significant improvements on previous bounds.

This page was built for publication: Reconstruction from smaller cards