3-reconstructibility of rooted trees

Alexandr V. Kostochka; Mina Nahvi; Douglas B. West; Dara Zirlin

doi:10.4310/pamq.2022.v18.n6.a7

3-reconstructibility of rooted trees

Alexandr V. Kostochka
, Mina Nahvi
, Douglas B. West
, Dara Zirlin

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

A rooted tree is ℓ-reconstructible if it is determined by its multiset of rooted subtrees (with the same root) obtained by deleting ℓ vertices. We determine which rooted trees are ℓ-reconstructible for ℓ ≤ 3 and show how this can be used to study reconstructibility of unrooted trees.

Original language	English (US)
Pages (from-to)	2479-2509
Number of pages	31
Journal	Pure and Applied Mathematics Quarterly
Volume	18
Issue number	6
DOIs	https://doi.org/10.4310/pamq.2022.v18.n6.a7
State	Published - 2022

Keywords

Reconstruction Conjecture
rooted tree
ℓ-reconstructibility

ASJC Scopus subject areas

General Mathematics

Online availability

10.4310/pamq.2022.v18.n6.a7

Library availability

Discover UIUC Full Text

Cite this

@article{c3cf5c66fcdf46ceb3c944d303b80865,

title = "3-reconstructibility of rooted trees",

abstract = "A rooted tree is ℓ-reconstructible if it is determined by its multiset of rooted subtrees (with the same root) obtained by deleting ℓ vertices. We determine which rooted trees are ℓ-reconstructible for ℓ ≤ 3 and show how this can be used to study reconstructibility of unrooted trees.",

keywords = "Reconstruction Conjecture, rooted tree, ℓ-reconstructibility",

author = "Kostochka, \{Alexandr V.\} and Mina Nahvi and West, \{Douglas B.\} and Dara Zirlin",

note = "arXiv: 1908.01258 Received June 28, 2021. 2010 Mathematics Subject Classification: Primary 05C60; secondary 05C05. \textbackslash{}u2217Research supported by NSF grant DMS-1600592 and NSF RTG grant DMS-1937241. \textbackslash{}u2020Research supported by Arnold O. Beckman Campus Research Board Award RB20003 of the University of Illinois at Urbana-Champaign. \textbackslash{}u2021Research supported by National Natural Science Foundation of China grants NSFC 11871439, 11971439, and U20A2068. \textbackslash{}u00A7Research 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.",

year = "2022",

doi = "10.4310/pamq.2022.v18.n6.a7",

language = "English (US)",

volume = "18",

pages = "2479--2509",

journal = "Pure and Applied Mathematics Quarterly",

issn = "1558-8599",

publisher = "International Press of Boston, Inc.",

number = "6",

}

TY - JOUR

T1 - 3-reconstructibility of rooted trees

AU - Kostochka, Alexandr V.

AU - Nahvi, Mina

AU - West, Douglas B.

AU - Zirlin, Dara

N1 - arXiv: 1908.01258 Received June 28, 2021. 2010 Mathematics Subject Classification: Primary 05C60; secondary 05C05. \u2217Research supported by NSF grant DMS-1600592 and NSF RTG grant DMS-1937241. \u2020Research supported by Arnold O. Beckman Campus Research Board Award RB20003 of the University of Illinois at Urbana-Champaign. \u2021Research supported by National Natural Science Foundation of China grants NSFC 11871439, 11971439, and U20A2068. \u00A7Research 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.

PY - 2022

Y1 - 2022

N2 - A rooted tree is ℓ-reconstructible if it is determined by its multiset of rooted subtrees (with the same root) obtained by deleting ℓ vertices. We determine which rooted trees are ℓ-reconstructible for ℓ ≤ 3 and show how this can be used to study reconstructibility of unrooted trees.

AB - A rooted tree is ℓ-reconstructible if it is determined by its multiset of rooted subtrees (with the same root) obtained by deleting ℓ vertices. We determine which rooted trees are ℓ-reconstructible for ℓ ≤ 3 and show how this can be used to study reconstructibility of unrooted trees.

KW - Reconstruction Conjecture

KW - rooted tree

KW - ℓ-reconstructibility

UR - https://www.scopus.com/pages/publications/85152388829

UR - https://www.scopus.com/pages/publications/85152388829#tab=citedBy

U2 - 10.4310/pamq.2022.v18.n6.a7

DO - 10.4310/pamq.2022.v18.n6.a7

M3 - Article

AN - SCOPUS:85152388829

SN - 1558-8599

VL - 18

SP - 2479

EP - 2509

JO - Pure and Applied Mathematics Quarterly

JF - Pure and Applied Mathematics Quarterly

IS - 6

ER -

3-reconstructibility of rooted trees

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this