Graph reconstruction numbers

Show full item record

Redirect: RIT Scholars content from RIT Digital Media Library has moved from to RIT Scholar Works, please update your feeds & links!
Title: Graph reconstruction numbers
Author: Brian, McMullen; Radziszowski, Stanislaw
Abstract: Proposed in 1942, the Graph Reconstruction Conjecture posits that every simple, finite, undirected graph with three or more vertices can be reconstructed up to isomorphism to the original graph, given the multiset of subgraphs produced by deleting each vertex along with its incident edges. Related to this Reconstruction Conjecture, existential reconstruction numbers, 9rn(G), concern the minimum number of vertex-deleted subgraphs required to identify a graph up to isomorphism. We discuss the resulting data from calculating reconstruction numbers for all simple, undirected graphs with up to ten vertices. From this data, we establish the reasons behind all high existential reconstruction numbers (9rn(G) > 3) for |V (G)| is less than or equal to 10 and identify new classes of graphs that have high reconstruction numbers for |V (G)| > 10. We also consider 2-reconstructibility { the ability to reconstruct a graph G from the multiset of subgraphs produced by deleting each combination of two vertices from G. The 2-reconstructibility of all graphs with nine or less vertices was tested, identifying four graphs in this range with five vertices as the highest order of graphs that are not 2-reconstructible.
Record URI:
Date: 2007

Files in this item

Files Size Format View
SRadziszowskiArticle2007.pdf 134.7Kb 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