Graph Reconstruction Numbers

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, $\mathrm{\exists }rn(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 ($\mathrm{\exists }rn(G)>3$) for $|V(G)|\le 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 fewer vertices was tested, identifying four graphs in this range with five vertices as the highest order of graphs that are not 2-reconstructible.