Switching reconstruction of digraphs

Importance: Medium ✭✭
Subject: Graph Theory
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 7th, 2013

\begin{question} Are there any switching-nonreconstructible digraphs on twelve or more vertices? \end{question}

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

The problem is a directed analogue of \OPrefnum[switching reconstruction of graphs]{46951} 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 \OPrefnum[Stanley's conjecture]{46951} that every simple graph on five or more vertices is switching-reconstructible.

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

Bibliography

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

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)


* indicates original appearance(s) of problem.