Kelly, Paul J.


Reconstruction conjecture ★★★★

Author(s): Kelly; Ulam

The \emph{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).

\begin{conjecture} If two graphs on $\ge 3$ vertices have the same deck, then they are isomorphic. \end{conjecture}

Keywords: reconstruction

Syndicate content