On the Reconstruction Conjecture
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Nicole Turpin Wall (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
- Advisor
- 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.
On the Reconstruction Conjecture
PDF (Portable Document Format)
244 KB
Created on 5/1/2008
Views: 5379
Additional Information
- Publication
- Thesis
- Language: English
- Date: 2008
- Keywords
- Reconstruction, Graphs, Trees, Kelly-Ulam, Nonreconstructable, Blocks
- Subjects
- Trees (Graph theory)
- Graph theory.