Home » Subject » Graph Theory
Importance: Outstanding ✭✭✭✭
Author(s): Kelly, Paul J.
Ulam, Stanislaw M.
Subject: Graph Theory
Keywords: reconstruction
Recomm. for undergrads: no
Posted by: zitterbewegung
on: October 18th, 2007

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.

See Wikipedia's Reconstruction Conjecture for more on this problem.

Bibliography

*[K] P. J. Kelly, A congruence theorem for trees, Pacific J. Math., 7 (1957), 961–968.

*[U] S. M. Ulam, A collection of mathematical problems, Wiley, New York, 1960.


* indicates original appearance(s) of problem.
3 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options