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

Posted by zitterbewegung
updated May 4th, 2010

3 comments

Graph Theory » Basic G.T.

Graham's conjecture on tree reconstruction ★★

Author(s): Graham

Problem for every graph $G$ , we let $L(G)$ denote the 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$ ?

Keywords: reconstruction; tree

Posted by mdevos
updated January 16th, 2013

5 comments

Open Problem Garden

reconstruction

Switching reconstruction conjecture ★★

Edge Reconstruction Conjecture ★★★

Reconstruction conjecture ★★★★

Graham's conjecture on tree reconstruction ★★

Navigate

Recent Activity