Multi-Vertex Deletion Graph Reconstruction Numbers

Abstract

First posed in 1942 by Kelly and Ulam, the Graph Reconstruction Conjecture is one of the major open problems in graph theory. While the Graph Reconstruction Conjecture remains open, 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) of these subgraphs are required to reconstruct $G$ up to isomorphism. This can then be extended to deleting $k$ vertices in every possible way.

Previous computer searches have found the 1-vertex-deletion reconstruction numbers of all graphs of up to 11 vertices. In this paper, computed values of $k$-vertex-deletion reconstruction numbers for all graphs on up to 8 vertices and $k\le |V(G)|–2$ are reported, as well as for some $k$ for graphs on 9 vertices. Our data suggested a number of new theorems and conjectures. In particular, we pose, as a generalization of the Graph Reconstruction Conjecture, that any graph on $3k$ or more vertices is $k$-vertex-deletion reconstructible.