Pure and Applied Mathematics Quarterly
Volume 18 (2022)
Special issue in honor of Fan Chung
Guest editors: Paul Horn, Yong Lin, and Linyuan Lu
$3$-reconstructibility of rooted trees
Pages: 2479 – 2509
A rooted tree is $\ell$-reconstructible if it is determined by its multiset of rooted subtrees (with the same root) obtained by deleting $\ell$ vertices. We determine which rooted trees are $\ell$-reconstructible for $\ell \leq 3$ and show how this can be used to study reconstructibility of unrooted trees.
Reconstruction Conjecture, $\ell$-reconstructibility, rooted tree
2010 Mathematics Subject Classification
Primary 05C60. Secondary 05C05.
The first-named author’s research was supported by NSF grant DMS-1600592 and NSF RTG grant DMS-1937241.
The second-named author’s research was supported by the Arnold O. Beckman Campus Research Board Award RB20003 of the University of Illinois at Urbana-Champaign.
The third-named author’s research was supported by National Natural Science Foundation of China grants NSFC 11871439, 11971439, and U20A2068.
The fourth-named author’s research was supported by NSF RTG grant DMS-1937241, and by Arnold O. Beckman Campus Research Board Award RB20003 of the University of Illinois at Urbana-Champaign.
Received 28 June 2021
Received revised 13 June 2022
Accepted 21 July 2022
Published 29 March 2023