Reconstruction of small graphs and digraphs

2021/02/03 by Brendan D. McKay, McKay, Brendan D. · 2 citations
Computer Science · #05C60 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2102.01942

openalex publication_date 2021/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We describe computer searches that prove the graph reconstruction conjecture for graphs with up to 13 vertices and some limited classes on larger sizes. We also investigate the reconstructibility of tournaments up to 13 vertices, digraphs up to 9 vertices, and posets up to 13 points. In all cases, our results also apply to the set reconstruction problem that uses the isomorph-reduced deck.

Citations

• A Census of Non-Reconstructable Digraphs, II: A Family of Tournaments

Cited by

• Semi-Random Graphs, Robust Asymmetry, and Reconstruction
• Shuffling the Deck: Invariant Theory and the Graph Reconstruction Conjecture

Related

• The Reconstruction of Graphs
• A Simple Explanation for the Reconstruction of Graphs
• Size reconstructibility of graphs
• An algebraic formulation of the graph reconstruction conjecture
• Reconstruction from smaller cards