Switching reconstruction of digraphs

Brendan D. McKay, Pascal Schweitzer

    Research output: Contribution to journalArticlepeer-review

    2 Citations (Scopus)

    Abstract

    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.

    Original languageEnglish
    Pages (from-to)279-296
    Number of pages18
    JournalJournal of Graph Theory
    Volume76
    Issue number4
    DOIs
    Publication statusPublished - Aug 2014

    Fingerprint

    Dive into the research topics of 'Switching reconstruction of digraphs'. Together they form a unique fingerprint.

    Cite this