Switching reconstruction of digraphs

DOI10.1002/JGT.21765MaRDI QIDQ5495887zbMATH OpenOpenAlexFDO

Authors Brendan D. McKay, P. Schweitzer

Publication date 7 August 2014

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.0675

zbMATH Keywords

digraphoriented graphreconstructionswitching

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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 non-reconstructible oriented graphs have 8 vertices, it is natural to ask whether there are any larger non-reconstructible graphs. In this paper we continue the investigation of this question. We find that there are exactly 44 non-reconstructible 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.

Recommendations

• Switching reconstruction of digraphs
• The \(r\)-switching-stable graphs
• Switching reconstruction and diophantine equations
• A note on the vertex-switching reconstruction
• Reconstruction from vertex-switching

Cites work

• A congruence theorem for trees
• Combinatorial reconstruction problems
• Graph reconstruction -- some new developments
• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• Reconstruction from vertex-switching
• Switching reconstruction of digraphs
• Vertex-switching reconstruction of subgraph numbers and triangle-free graphs

Cited in

(7)

• Degree conditions for vertex switching reconstruction
• Parity of sets of mutually orthogonal Latin squares
• The \(r\)-switching-stable graphs
• Reconstructing Digraphs from Partial Dadecks
• scientific article; zbMATH DE number 1522565 (Why is no real title available?)
• Switching reconstruction of digraphs
• Switchings, extensions, and reductions in central digraphs

This page was built for publication: Switching reconstruction of digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495887)