2021/12/02 by Hunter, Zach
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2112.01094
For a graph G, the ℓ-deck of G is the multiset of induced subgraphs on G having ℓ vertices. Recently, Groenland et al. proved that any tree can be reconstructed from its (8/9+o(1))n-deck. For the particular case of caterpillar graphs, we show that the (1/2+o(1))n-deck suffices, which is asymptotically tight.