The Reconstruction of a Tree from its Maximal Subtrees
- 1 January 1966
- journal article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 18, 803-810
- https://doi.org/10.4153/cjm-1966-079-8
Abstract
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.Keywords
This publication has 1 reference indexed in Scilit:
- A congruence theorem for treesPacific Journal of Mathematics, 1957