Importance: Medium ✭✭
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: fhavet
on: March 7th, 2013
Question   Are there any switching-nonreconstructible digraphs on twelve or more vertices?

To switch a vertex of a digraph is to reverse all the arcs incident to it. The digraph so obtained is called a switching of the digraph. The collection of switchings of a digraph $ D $ is called the switching deck of $ D $. A digraph is switching-reconstructible if every digraph with the same deck as $ D $ is isomorphic to $ D $.

The problem is a directed analogue of switching reconstruction of graphs in which one complements the edges at a vertex, instead of reversing each of its incident arcs.

Bondy and Mercier proved an analogue to Stanley's result for switching reconstruction of graphs. They proved that a digraph on $ n $ vertices is switching-reconstructible if $ n \not\equiv 0 (\mod 4) $. They also proved many other common results for both switching reconstructions.

One significant difference between the directed and undirected problems is that there exist switching-nonreconstructible directed graphs on eight vertices, while Stanley's conjecture that every simple graph on five or more vertices is switching-reconstructible.


*[BM] J. A. Bondy and F. Mercier. Switching reconstruction of digraphs. J. Graph Theory 67(2011), no. 4, 332-348.

* indicates original appearance(s) of problem.


Comments are limited to a maximum of 1000 characters.
More information about formatting options