Kelly, Paul J.


Reconstruction conjecture ★★★★

Author(s): Kelly; Ulam

The deck of a graph $ G $ is the multiset consisting of all unlabelled subgraphs obtained from $ G $ by deleting a vertex in all possible ways (counted according to multiplicity).

Conjecture   If two graphs on $ \ge 3 $ vertices have the same deck, then they are isomorphic.

Keywords: reconstruction

Syndicate content