A computational investigation of graph reconstruction

Show full item record

Redirect: RIT Scholars content from RIT Digital Media Library has moved from http://ritdml.rit.edu/handle/1850/5489 to RIT Scholar Works http://scholarworks.rit.edu/theses/6932, please update your feeds & links!
Title: A computational investigation of graph reconstruction
Author: Rivshin, David
Abstract: First proposed in 1941 by Kelly and Ulam, the Graph Reconstruction Conjecture has been called the major open problem in the field of Graph Theory. While the Graph Reconstruction Conjecture is still unproven it has spawned a number of related questions. In the classical vertex graph reconstruction number problem a vertex is deleted in every possible way from a graph G, and then it can be asked how many (both minimum and maximum values) of these subgraphs are required to uniquely reconstruct G (up to isomorphism). This problem can then be extended to k-vertex deletion (for 1 ≤ k ≤ |V (G)|), and to k-edge deletion (for 1 ≤ k ≤ |E(G)|). For some classes of graphs there is known a formula to directly compute its reconstruction numbers. However, for the vast majority of graphs the computation devolves to brute force exhaustive search. Previous computer searches have computed the 1-vertex-deletion reconstruction numbers of all graphs of up to 10 vertices, as well as computing 2-vertex-deletion reconstructibility of all graphs on up to 9 vertices. In this project I have developed and implemented an improved algorithm to compute 1-vertex-deletion reconstruction numbers with an O(|V (G)|) speedup, allowing their computation for all graphs of up to 11 vertices. In addition the ability to compute arbitrary k-vertex and edge deletion reconstruction numbers has been implemented, leading to many new results in these areas.
Record URI: http://hdl.handle.net/1850/5489
Date: 2008

Files in this item

Files Size Format View
DRivshinMasterProject2007.pdf 463.5Kb PDF View/Open
DRivshinProposal2007.pdf 138.5Kb 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