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

DOI10.1016/J.INS.2023.119858MaRDI QIDQ6151923zbMATH OpenFDO

Authors Robert John O'Shea, Louis Wilkins

Publication date 12 February 2024

Published in Information Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/J.INS.2023.119858

zbMATH Keywords

graph isomorphismgraph recognitionhypomorphismquadratric assignmentreconstructible graphsreconstruction conjecture

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5287238
• Graph reconstruction from subgraphs
• Progress on the reconstruction conjecture
• The reconstruction conjecture for finite simple graphs and associated directed graphs
• An algebraic formulation of the graph reconstruction conjecture

Cites work

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

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

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