Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-20T16:35:06.379Z Has data issue: false hasContentIssue false
  • English
  • Français

The Reconstruction of a Tree from its Maximal Subtrees

Published online by Cambridge University Press:  20 November 2018

Frank Harary  and
Ed Palmer
Frank Harary
Affiliation:
The University of Michigan, Ann Arbor, Michigan
Ed Palmer
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.

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.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 18 , 1966 , pp. 803 - 810
Copyright
Copyright © Canadian Mathematical Society 1966

References

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. Harary, F. and Palmer, E., On similar points of a graph, J. Math. Mech. 15 (1966), to appear.Google Scholar
3. Kelly, P. J., A congruence theorem for trees, Pacific J. Math., 7 (1957), 961–968.Google Scholar
4. König, D., Theorie der endlichen und unendlichen Graphen (Leipzig, 1936; reprinted New York, 1950).Google Scholar
5. Ulam, S. M., A collection of mathematical problems (New York, 1960). p. 29.Google Scholar