Switching reconstruction conjecture

Importance: Medium ✭✭
Author(s): Stanley, Richard P.
Subject: Graph Theory
Keywords: reconstruction
Recomm. for undergrads: no
Posted by: fhavet
on: March 7th, 2013
Conjecture   Every simple graph on five or more vertices is switching-reconstructible.

To switch a vertex of a simple graph is to exchange its sets of neighbours and non-neighbours. The graph so obtained is called a switching of the graph. The collection of switchings of a graph G is called the switching deck of $ G $. A graph is switching-reconstructible if every graph with the same deck as $ G $ is isomorphic to $ G $.

There are four pairs of non-isomorphic graphs of order $ 4 $ with the same switching deck. One of them consists of the empty graph and the $ 4 $-cycle.

Stanley [S] proved that a graph on $ n $ vertices is switching-reconstructible if $ n \not\equiv 0 (\mod 4) $.

An analogous problem was posed for digraphs. Instead of complementing the edges at a vertex, one reverses each of its incident arc.


*[S] R. P. Stanley Reconstruction from vertex-switching. J. Combin. Theory Ser. B, 38 (1985), 132--138.

* indicates original appearance(s) of problem.