Graph reconstruction numbers

Show full item record

Title: Graph reconstruction numbers
Author: Baldwin, Jennifer
Abstract: One of the most important open questions in graph theory is the graph reconstruction conjecture, first proposed by P. J. Kelly and S. M. Ulam in 1941. The conjecture states that every graph with at least 3 vertices is reconstructible if there exists some multi-subset of vertex-deleted subgraphs that reconstructs G uniquely up to isomorphism. This project computes the existential and universal reconstruction numbers for all graphs of order at most nine. The existential reconstruction number is the number of vertex-deleted subgraphs, or cards, required to reconstruct G uniquely up to isomorphism. The universal reconstruction number is the minimum num- ber of cards for which all multi-subsets of that size reconstruct G uniquely up to isomorphism. The graph reconstruction conjecture is still unproven, but the results of this project help provide more information. Many theorems relating to the existential reconstruction number were verified by my results. The universal reconstruction number has been researched very little so far. The reconstruction numbers produced by this project help support the opinion that most graphs are easily reconstructible.
Record URI: http://hdl.handle.net/1850/2745
Date: 2006

Files in this item

Files Size Format View
JBaldwinMasterProject2003.pdf 876.8Kb PDF View/Open
JBaldwinProposal2003.pdf 69.29Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse