Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs

DOI10.1016/j.ins.2023.119858MaRDI QIDQ6151923

Louis Wilkins, Robert John O'Shea

Publication date: 12 February 2024

Published in: Information Sciences (Search for Journal in Brave)

zbMATH Keywords

reconstruction conjecturegraph isomorphismhypomorphismgraph recognitionreconstructible graphsquadratric assignment

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Computational complexity of reconstruction and isomorphism testing for designs and line graphs
• A congruence theorem for trees
• Reconstructible graphs, simplicial flag complexes of homology manifolds and associated right-angled Coxeter groups
• A family of non-reconstructible hypergraphs
• Reconstruction of infinite graphs
• Some work towards the proof of the reconstruction conjecture
• Reconstruction of distance hereditary 2-connected graphs
• A new approach to graph reconstruction using supercards
• Graph reconstruction -- some new developments
• Non-reconstructible locally finite graphs
• On the reconstruction of the characteristic polynomial of a graph
• The reconstruction conjecture for finite simple graphs and associated directed graphs
• Are all pairs of hypomorphic digraphs \(S\)-isomorphic?
• A uniqueness theorem on matrices and reconstruction
• The polynomial reconstruction problem: the first 50 years
• A TOPOLOGICAL VARIATION OF THE RECONSTRUCTION CONJECTURE
• Reconstruction of matrices from submatrices
• Reconstruction of a graph from 2–vicinities of its vertices
• The reconstruction conjecture is true if all 2-connected graphs are reconstructible
• The Multiple Sequence Alignment Problem in Biology
• THE RELATIONSHIP BETWEEN THE COMPUTATIONAL COMPLEXITIES OF THE LEGITIMATE DECK AND ISOMORPHISM PROBLEMS
• On Reconstruction of Matrices
• The falsity of the reconstruction conjecture for tournaments
• Graph reconstruction—a survey
• On the complexity of graph reconstruction
• Reconstruction from the deck of ‐vertex induced subgraphs
• On Reconstruction of Graphs From the Multiset of Subgraphs Obtained by Deleting ℓ Vertices
• A property of most of the known non-reconstructible digraphs
• Reconstruction of small graphs and digraphs
• The connected partition lattice of a graph and the reconstruction conjecture
• Mathematical Foundations of Computer Science 2004
• Ulam's Conjecture and Graph Reconstructions
• Seurat games on Stockmeyer graphs

This page was built for publication: Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs