The reconstruction of a tree from its number deck
type: Item
instance of: scholarly article
title: The reconstruction of a tree from its number deck
zbMATH Open document ID: 0565.05021
DOI: 10.1016/0012-365X(85)90136-0
author: J. Schönheim
author: Ilia Krasikov
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: Let T be a tree, \(v_ i\) an internal node of T and \(v'_ i\) the vector whose components are the number of nodes in the trees of the forest obtained by deleting \(v_ i\). The collection of vectors \(v'_ i\) is called the number deck of T. The paper answers a question of Caro and Schönheim whether a tree T is determined by its number deck up to isomorphism by giving a necessary and sufficient condition for reconstructibility. The proof includes an algorithm that constructs all nonisomorphic trees having a given number deck.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 3900778
zbMATH Keywords: tree
zbMATH Keywords: number deck
zbMATH Keywords: reconstructibility
reviewed by: Peter Kirschenhofer
MaRDI profile type: Publication
cites work: Q5557023
cites work: Q3901534
cites work: Q5544087
cites work: The Reconstruction of a Tree from its Maximal Subtrees
cites work: A congruence theorem for trees
cites work: Q5555548
full work available at URL: 0012-365x(85)90136-0
OpenAlex ID: W2075019347
description: scientific article; zbMATH DE number 3900778