Optimally reconstructing caterpillars

MaRDI QIDQ6384627zbMATH OpenFDO

Authors Zach Hunter

Publication date 2 December 2021

Abstract: For a graph $G$, the $ell$-deck of $G$ is the multiset of induced subgraphs on $G$ having $ell$ 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.

This page was built for publication: Optimally reconstructing caterpillars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6384627)