On the Reconstruction Conjecture

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Nicole Turpin Wall (Creator)
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/
Paul Duvall

Abstract: "Every graph of order three or more is reconstructible." Frank Harary restated one of the most famous unsolved problems in graph theory. In the early 1900's, while one was working on his doctoral dissertation, two mathematicians made a conjecture about the reconstructibility of graphs. This came to be known as the Reconstruction Conjecture or the Kelly-Ulam Conjecture. The conjecture states: Let G and H be graphs with V(G) = {v_1, v_2, ..., v_n}, V(H) = {u_1, u_2, ..., u_n}, n greater than or equal to 3. If G - v_i is isomorphic to H - u_i for all i = 1, ..., n, then G is isomorphic to H. Much progress has been made toward showing that this statement is true for all graphs. This paper will discuss some of that progress, including some of the families of graphs which we know that the conjecture is true. Another big field of interest about the Reconstruction Conjecture is the information that is retained by a graph when we begin looking at its vertex-deleted subgraphs. Many graph theorists believe that this may show us more about the conjecture as a whole. While working on a possible proof to the Reconstruction Conjecture, many mathematicians began to think about different approaches. One approach that was fairly common was to relate the Reconstruction Conjecture to edges of a graph instead of the vertices. People realized that when deleting only one edge of a graph, then logically more information about the original graph would be retained.

Additional Information

Language: English
Date: 2008
Reconstruction, Graphs, Trees, Kelly-Ulam, Nonreconstructable, Blocks
Trees (Graph theory)
Graph theory.

Email this document to