Open Problem Garden - Reconstruction conjecture - Comments

A strategy for simple graphs? (re: Reconstruction conjecture)

Anonymous — Tue, 04 May 2010 00:09:15 +0200

How about 1) Prove for a 4-node, or tetrahedral graph. 2) Demonstrate that all graphs with > 4 nodes are composed of multiple overlapping tetrahedrons 3) Figure out how coupled tetrahedra function when nodes are deleted. 4) Induct on number of tetrahedra in graph. ?

Obviously (3) is the tough part, but why should it be impossible?

correction and partial results (re: Reconstruction conjecture)

melch — Fri, 23 May 2008 09:02:36 +0200

this should be on 3 or more vertices. False for digraphs, hypergraphs, and infinite graphs. It is open for simple graphs and multigraphs

Question. (re: Reconstruction conjecture)

Anonymous — Wed, 28 Nov 2007 16:45:15 +0100

Does G have to be simple, or can it be a multigraph?

Reconstruction conjecture

zitterbewegung — Thu, 18 Oct 2007 14:35:42 +0200

Author(s): Kelly; Ulam

Subject: Graph Theory

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

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