Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-19T02:16:47.721Z Has data issue: false hasContentIssue false

Reconstruction of Trees

Published online by Cambridge University Press:  20 November 2018

Bennet Manvel*
Affiliation:
The University of Michigan, Ann Arbor, Michigan
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Every tree T determines a set of distinct maximal proper subtrees Ti = T — vi , which are obtained by the deletion of an endpoint of T. In this paper we prove that a tree is almost always uniquely determined by this set of its subtrees, and point out two interesting consequences of this result.

In [5], Ulam proposed the following conjecture, which we state in a slightly stronger form due to Harary [1].

ULAM'S CONJECTURE. A graph G with at least three points is uniquely determined up to isomorphism by the subgraphs Gi = G — vi .

Kelly [4] proved the conjecture for trees and Harary and Palmer [3] showed that not all of the Gi are needed in that case by proving Corollary 1 below. If we remove from the list of subgraphs Gi of a graph G all but one graph of each isomorphism type, we obtain a set of Gi which are distinct up to isomorphism.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1970