The reconstruction of a tree from its number deck
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.
scientific article; zbMATH DE number 3900778