Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-25T16:31:12.088Z Has data issue: false hasContentIssue false

A note on the edge reconstruction conjecture

Published online by Cambridge University Press:  17 April 2009

E.F. Schmeichel
Affiliation:
Department of Mathematics, University of Southern California, Los Angeles, California, USA
Rights & Permissions [Opens in a new window]

Abstract

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.

Let G be a graph with vertex degree sequence d1d2 ≤ … ≤ dp It is shown that if di + dpi+1p for some i, then G is uniquely reconstructable from its collection of maximal (edge deleted) subgraphs. This generalizes considerably a result of Lovász. As a corollary, it is shown that Chvátal's existence condition for hamiltonian cycles implies edge reconstructability as well.

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1975

References

[1]Chvátal, V., “On Hamilton's ideals”, J. Combinatorial Theory Ser. B.12 (1972), 163168.CrossRefGoogle Scholar
[2]Greenwell, D.L. and Hemminger, R.L., “Reconstructing graphs”, The many facets of graph theory, 91114 (Lecture Notes in Mathematics, 110. Springer-Verlag, Berlin, Heidelberg, New York, 1969).CrossRefGoogle Scholar
[3]Harary, F., “On the reconstruction of a graph from a collection of subgraphs”, Theory of graphs and -its applications, 4752 (Proc. Sympos., Smolenice, 06 1963. Publishing House of the Czechoslovak Academy of Sciences, Prague, 1964).Google Scholar
[4]Kelly, Paul J., “A congruence theorem for trees”, Pacific J. Math. 7 (1957), 961968.CrossRefGoogle Scholar
[5]Lovász, L., “A note on the line reconstruction problem“, J. Combinatorial Theory Ser. B 13 (1972), 309310.CrossRefGoogle Scholar
[6]Ulam, S.M., A collection of mathematical problems (Interscience, New York, London, 1960).Google Scholar