Pure and Applied Mathematics Quarterly

Volume 18 (2022)

Number 6

Special issue in honor of Fan Chung

Guest editors: Paul Horn, Yong Lin, and Linyuan Lu

$3$-reconstructibility of rooted trees

Pages: 2479 – 2509

DOI: https://dx.doi.org/10.4310/PAMQ.2022.v18.n6.a7

Authors

Alexandr V. Kostochka (University of Illinois, Urbana, Il., U.S.A.)

Mina Nahvi (University of Illinois, Urbana, Il., U.S.A.)

Douglas B. West (University of Illinois, Urbana, Il., U.S.A.)

Dara Zirlin (University of Illinois, Urbana, Il., U.S.A.)

Abstract

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.

Keywords

Reconstruction Conjecture, $\ell$-reconstructibility, rooted tree

2010 Mathematics Subject Classification

Primary 05C60. Secondary 05C05.

Full Text (PDF format)

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