Reconstructing graphs
HTML articles powered by AMS MathViewer
- by D. L. Greenwell PDF
- Proc. Amer. Math. Soc. 30 (1971), 431-433 Request permission
Abstract:
Every graph G determines a collection M of maximal vertex proper subgraphs ${G_i} = G - {v_i}$ and a collection M’ of maximal edge proper subgraphs ${G^i} = G - {e_i}$. In this paper we prove that a graph G, on at least three edges and without isolated vertices, can be reconstructed, up to isomorphism, from the collection M’ if it can be reconstructed, up to isomorphism, from the collection M.References
- D. L. Greenwell and R. L. Hemminger, Reconstructing graphs, The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) Springer, Berlin, 1969, pp. 91–114. MR 0252258
- F. Harary, On the reconstruction of a graph from a collection of subgraphs, Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Publ. House Czech. Acad. Sci., Prague, 1964, pp. 47–52. MR 0175111
- Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911
- Robert L. Hemminger, On reconstructing a graph, Proc. Amer. Math. Soc. 20 (1969), 185–187. MR 232696, DOI 10.1090/S0002-9939-1969-0232696-4
- S. M. Ulam, A collection of mathematical problems, Interscience Tracts in Pure and Applied Mathematics, no. 8, Interscience Publishers, New York-London, 1960. MR 0120127
Additional Information
- © Copyright 1971 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 30 (1971), 431-433
- MSC: Primary 05.40
- DOI: https://doi.org/10.1090/S0002-9939-1971-0286699-3
- MathSciNet review: 0286699