Geodesic
The Reconstruction of a Tree from its Maximal Subtrees
Canadian journal of mathematics, Tome 18 (1966) no. 1, pp. 803-810

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

One of the many interesting conjectures proposed by S. M. Ulam in (5) can be stated as follows:If G and H are two graphs with p points vi and ui respectively (p ⩾ 3) such that for all i, G — vi is isomorphic with H — ui then G and H are themselves isomorphic.P. J. Kelly (3) has shown this to be true for trees. The conjecture is, of course, not true for p = 2, but Kelly has verified by exhaustion that it holds for all of the other graphs with at most six points. Harary and Palmer (2) found the same to be true of the seven-point graphs.In (1) Harary reformulated the conjecture as a problem of reconstructing G from its subgraphs G — vi and derived several of the invariants of G from the collection G — vi. 
Harary, Frank; Palmer, Ed. The Reconstruction of a Tree from its Maximal Subtrees. Canadian journal of mathematics, Tome 18 (1966) no. 1, pp. 803-810. doi: 10.4153/CJM-1966-079-8
@article{10_4153_CJM_1966_079_8,
     author = {Harary, Frank and Palmer, Ed},
     title = {The {Reconstruction} of a {Tree} from its {Maximal} {Subtrees}},
     journal = {Canadian journal of mathematics},
     pages = {803--810},
     year = {1966},
     volume = {18},
     number = {1},
     doi = {10.4153/CJM-1966-079-8},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1966-079-8/}
}
TY  - JOUR
AU  - Harary, Frank
AU  - Palmer, Ed
TI  - The Reconstruction of a Tree from its Maximal Subtrees
JO  - Canadian journal of mathematics
PY  - 1966
SP  - 803
EP  - 810
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1966-079-8/
DO  - 10.4153/CJM-1966-079-8
ID  - 10_4153_CJM_1966_079_8
ER  - 
%0 Journal Article
%A Harary, Frank
%A Palmer, Ed
%T The Reconstruction of a Tree from its Maximal Subtrees
%J Canadian journal of mathematics
%D 1966
%P 803-810
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1966-079-8/
%R 10.4153/CJM-1966-079-8
%F 10_4153_CJM_1966_079_8

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

[2] 2. Harary, F. and Palmer, E., On similar points of a graph, J. Math. Mech. 15 (1966), to appear. Google Scholar

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

[4] 4. König, D., Theorie der endlichen und unendlichen Graphen (Leipzig, 1936; reprinted New York, 1950). Google Scholar

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

Cité par Sources :