Geodesic
Reconstruction of Trees
Canadian journal of mathematics, Tome 22 (1970) no. 1, pp. 55-60

Voir la notice de l'article provenant de la source Cambridge University Press

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. 
Manvel, Bennet. Reconstruction of Trees. Canadian journal of mathematics, Tome 22 (1970) no. 1, pp. 55-60. doi: 10.4153/CJM-1970-007-4
@article{10_4153_CJM_1970_007_4,
     author = {Manvel, Bennet},
     title = {Reconstruction of {Trees}},
     journal = {Canadian journal of mathematics},
     pages = {55--60},
     year = {1970},
     volume = {22},
     number = {1},
     doi = {10.4153/CJM-1970-007-4},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1970-007-4/}
}
TY  - JOUR
AU  - Manvel, Bennet
TI  - Reconstruction of Trees
JO  - Canadian journal of mathematics
PY  - 1970
SP  - 55
EP  - 60
VL  - 22
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1970-007-4/
DO  - 10.4153/CJM-1970-007-4
ID  - 10_4153_CJM_1970_007_4
ER  - 
%0 Journal Article
%A Manvel, Bennet
%T Reconstruction of Trees
%J Canadian journal of mathematics
%D 1970
%P 55-60
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1970-007-4/
%R 10.4153/CJM-1970-007-4
%F 10_4153_CJM_1970_007_4

[1] 1. Harary, F., On the reconstruction of a graph from a collection of subgraphs, pp. 47–52 in Theory of graphs and its applications, edited by Fiedler, M. (Academic Press, New York, 1964). Google Scholar

[2] 2. Harary, F., Graph theory (Addison-Wesley, Reading, Massachusetts 1969). Google Scholar

[3] 3. Harary, F. and Palmer, E. M., The reconstruction of a tree from its maximal subtrees, Can. J. Math. 18 (1966), 803–810. Google Scholar

[4] 4. Kelly, P. J., A congruence theorem for trees, Pacific J. Math. 7 (1957), 961–968. Google Scholar

[5] 5. Ulam, S. M., A collection of mathematical problems, p. 29 (Wiley (Interscience), New York, 1960). Google Scholar

Cité par Sources :