Reconstruction of Trees
- 1 February 1970
- journal article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 22 (1) , 55-60
- https://doi.org/10.4153/cjm-1970-007-4
Abstract
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.Keywords
This publication has 1 reference indexed in Scilit:
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969