Vol. 52, No. 2, 1974

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 329: 1  2
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author index
To appear
Other MSP journals
Reconstructing infinite graphs

J. Adrian (John) Bondy and Robert Louis Hemminger

Vol. 52 (1974), No. 2, 331–340

It is a well-known conjecture of S. M. Ulam that any finite graph of order at least three can be reconstructed from its maximal vertex-deleted subgraphs. Formally (writing Gv for G v) Ulam’s Conjecture states: if G and H are finite graphs of order at least three such that there is a bijection σ;V (G) V (H) with the property (1) GvHσ(v) for all v V (G), then GH. This conjecture has not been proved in general, although it was shown by P. J. Kelly to be true for disconnected graphs and trees and has also been verified for several other classes of graphs. The purpose of this paper is to examine Ulam’s Conjecture for infinite graphs. (It is trivial to determine, from any Gv, whether or not a graph G is infinite.) Results are obtained which can loosely be viewed as extensions of Kelly’s work on disconnected graphs and trees.

Mathematical Subject Classification 2000
Primary: 05C05
Received: 1 March 1972
Revised: 17 October 1973
Published: 1 June 1974
J. Adrian (John) Bondy
Robert Louis Hemminger