Reconstruction of small graphs and digraphs

MaRDI QIDQ5090542zbMATH OpenFDO

Authors Brendan D. McKay

Publication date 20 July 2022

Full work available at URL https://arxiv.org/abs/2102.01942, http://ajc.maths.uq.edu.au/pdf/83/ajc_v83_p448.pdf

zbMATH Keywords

graph reconstruction conjecture

Mathematics Subject Classification ID

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

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.

Recommendations

• scientific article; zbMATH DE number 1051281
• The vertex and edge graph reconstruction numbers of small graphs
• The graph reconstruction number
• Graph reconstruction -- some new developments
• Progress on the reconstruction conjecture

Cites work

• A census of non-reconstructable digraphs. I: Six related families
• Computer reconstruction of small graphs
• Generating the Nine-Point Graphs
• scientific article; zbMATH DE number 4097431 (Why is no real title available?)
• scientific article; zbMATH DE number 3504998 (Why is no real title available?)
• scientific article; zbMATH DE number 1051281 (Why is no real title available?)
• scientific article; zbMATH DE number 3258862 (Why is no real title available?)
• Isomorph-Free Exhaustive Generation
• On nonreconstructable tournaments
• On reconstructing graphs from their sets of subgraphs
• On reconstruction of graphs
• On Stockmeyer's non-reconstructible tournaments
• On the problem of reconstructing a tournament from subtournaments
• Posets on up to 16 points
• Practical graph isomorphism. II.
• The falsity of the reconstruction conjecture for tournaments
• What is reconstruction for ordered sets?

Cited in

(10)

• Graphical partially ordered sets
• The vertex and edge graph reconstruction numbers of small graphs
• scientific article; zbMATH DE number 3869374 (Why is no real title available?)
• Reconstructing Digraphs from Partial Dadecks
• scientific article; zbMATH DE number 4162908 (Why is no real title available?)
• scientific article; zbMATH DE number 3948325 (Why is no real title available?)
• scientific article; zbMATH DE number 1051281 (Why is no real title available?)
• Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs
• A characterization of generalized cospectrality of rooted graphs with applications in graph reconstruction
• Complexity results in graph reconstruction

This page was built for publication: Reconstruction of small graphs and digraphs

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