Switching Reconstruction of Digraphs. Issue 4 (11th September 2013)

• Record Type: Journal Article
• Authors: McKay, Brendan D.; Schweitzer, Pascal
• Is Part Of: Journal of graph theory. Volume 76:Issue 4(2014)
• Page Start: 279
• Page End: 296
• Publication Date: 2013-09-11
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21765
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Switching about a vertex in a digraph means to reverse the direction of every edge incident with that vertex. Bondy and Mercier introduced the problem of whether a digraph can be reconstructed up to isomorphism from the multiset of isomorphism types of digraphs obtained by switching about each vertex. Since the largest known nonreconstructible oriented graphs have eight vertices, it is natural to ask whether there are any larger nonreconstructible graphs. In this article, we continue the investigation of this question. We find that there are exactly 44 nonreconstructible oriented graphs whose underlying undirected graphs have maximum degree at most 2. We also determine the full set of switching‐stable oriented graphs, which are those graphs for which all switchings return a digraph isomorphic to the original.</p> </abstract>