TOPICS
Search

Hypomorphic Graphs


A graph G is said to be hypomorphic to a graph H if G and H have the same graph deck. Equivalently, G is hypomorphic to H precisely when the vertices of G and H can be put in bijection, say by phi:V(G)->V(H), so that the graph card G-v is isomorphic to H-phi(v) for every vertex v of G.

A graph is reconstructible if it has no nonisomorphic hypomorphic mate. The graph reconstruction conjecture asserts that every simple finite graph on at least three vertices is reconstructible.


See also

Graph Card, Graph Deck, Graph Reconstruction Conjecture, Isomorphic Graphs, Reconstructible Graph, Vertex-Induced Subgraph

Explore with Wolfram|Alpha

References

Kocay, W. L. "Hypomorphisms, Orbits, and Reconstruction." J. Combin. Th. Ser. B 44, 187-200, 1988.

Cite this as:

Weisstein, Eric W. "Hypomorphic Graphs." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HypomorphicGraphs.html

Subject classifications