Switching reconstruction conjecture ★★

Author(s): Stanley

\begin{conjecture} Every simple graph on five or more vertices is switching-reconstructible. \end{conjecture}

Keywords: reconstruction

Edge Reconstruction Conjecture ★★★

Author(s): Harary

\begin{conjecture} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. Every simple graph with at least 4 edges is reconstructible from it's edge deleted subgraphs \end{conjecture}

Keywords: reconstruction

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

Graham's conjecture on tree reconstruction ★★

Author(s): Graham

\begin{problem} for every graph $G$, we let $L(G)$ denote the \Def{line graph} of $G$. Given that $G$ is a tree, can we determine it from the integer sequence $|V(G)|, |V(L(G))|, |V(L(L(G)))|, \ldots$? \end{problem}

Keywords: reconstruction; tree

Syndicate content