The Vertex-Switching Reconstruction Problem

Abstract

Switching on a vertex of a graph involves swapping the sets of neighbours and non-neighbours of the vertex. The resultant graph is called a switch card of the original graph. The switch deck of a graph is the collection of all of its switch cards. The vertex-switch reconstruction problem then asks which graphs (termed non-VSR graphs) cannot be uniquely determined from their switch decks. A review of the published knowledge about this problem is followed by an improved bound on the number of edges in a non-VSR graph, and a bound on the size of the automorphism group of a non-VSR graph. Finally, the results of a computer search are presented, showing that no non-VSR graphs of order 8 or 12 exist.