Hypomorphisms, orbits, and reconstruction

DOI10.1016/0095-8956(88)90087-1MaRDI QIDQ1077435zbMATH OpenOpenAlexFDO

Authors William Kocay

Publication date 1988

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(88)90087-1

zbMATH Keywords

graph reconstructionhypomorphic graphshypomorphismorbitspartial automorphismreconstruction conjecture

Mathematics Subject Classification ID

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

Review text

Graphs G and H are hypomorphic if there is a bijection \(\phi\) : V(G)\(\to V(H)\) such that G-u\(\cong H-\phi (u)\), for all \(u\in V(G)\). The reconstruction conjecture states that hypomorphic graphs are isomorphic, if G has at least three vertices. We investigate properties of the isomorphisms G-u\(\cong H-\phi (u)\), and their relation to the reconstructibility of G.

Recommendations

• On a reconstruction problem
• Progress on the reconstruction conjecture
• Properties of non-reconstructible graphs and digraphs
• scientific article; zbMATH DE number 4097431
• Hypomorphy of graphs up to complementation

Cites work

• A census of non-reconstructable digraphs. I: Six related families
• A family of non-reconstructible hypergraphs
• Graph reconstruction—a survey
• Graph theory with applications
• scientific article; zbMATH DE number 3674136 (Why is no real title available?)
• On Stockmeyer's non-reconstructible tournaments
• On the reconstruction of a graph from its closure function
• The falsity of the reconstruction conjecture for tournaments

Cited in

(17)

• Reconstruction of locally finite connected graphs with two infinite wings
• The k-orbit reconstruction and the orbit algebra
• \((-1)\)-hypomorphic graphs with the same 3-element homogeneous subsets
• Non-reconstructible locally finite graphs
• The reconstruction conjecture for finite simple graphs and associated directed graphs
• Are all pairs of hypomorphic digraphs S-isomorphic?
• Hypomorphy of graphs up to complementation
• Reconstructing the number of blocks of an infinite graph
• Graph reconstruction by permutations
• scientific article; zbMATH DE number 3853124 (Why is no real title available?)
• scientific article; zbMATH DE number 4097431 (Why is no real title available?)
• Algebraic Hulls and Smooth Orbit Equivalence
• Properties of non-reconstructible graphs and digraphs
• scientific article; zbMATH DE number 1409216 (Why is no real title available?)
• A property of most of the known non-reconstructible digraphs
• The edge-subgraph poset of a graph and the edge reconstruction conjecture
• The double reconstruction conjecture about finite colored hypergraphs

This page was built for publication: Hypomorphisms, orbits, and reconstruction

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