Reconstruction conjecture

From Wikipedia, the free encyclopedia

Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly^[1] and Ulam^[2].

1 Formal statement
2 Verification
3 Other structures
4 Further reading
5 References

[edit] Formal statement

Given a graph $G = (V, E)$ , a vertex-deleted subgraph of $G$ is an induced subgraph formed by deleting exactly one vertex from $G$ .

For a graph $G$ , the deck of G, denoted $D (G)$ , is the collection of all vertex-deleted subgraphs of $G$ . Note that in general this is not a set, but a multiset, since two vertex deleted subgraphs may be isomorphic, but we still want to count their multiplicity. Each graph in $D (G)$ is called a card.

With these definitions, the conjecture can be stated as:

Reconstruction Conjecture: Any two graphs on at least three vertices with the same decks are isomorphic.

(The requirement that the graphs have at least three vertices is necessary because both graphs on two vertices have the same decks.)

Harary^[3] suggested a stronger version of the conjecture:

Set Reconstruction Conjecture: Any two graphs on at least four vertices with the same sets of vertex-deleted induced subgraphs are isomorphic.

[edit] Verification

The conjecture has been verified for a number of infinite classes of graphs, such as regular graphs (graphs in which all vertices have the same number of edges attached to them).

Both the reconstruction and set reconstruction conjectures have been verified for all graphs with at most 11 vertices (McKay^[4]).

In a probabilistic sense, it has been shown (Bollobás^[5]) that almost all graphs are reconstructible. This means that the probability that a randomly chosen graph on $n$ vertices is not reconstructible goes to 0 as $n$ goes to infinity. In fact, it was shown that not only are almost all graphs reconstructible, but in fact that the entire deck is not necessary to reconstruct them — almost all graphs have the property that there exist three cards in their deck that uniquely determine the graph.

[edit] Other structures

It has been shown that the following are not in general reconstructible:

Digraphs (Stockmeyer^[6])
Hypergraphs (Kocay^[7])
Infinite graphs

[edit] Further reading

For further information on this topic, see the survey by Nash-Williams^[8].

[edit] References

^ Kelly, P. J., A congruence theorem for trees, Pacific J. Math., 7 (1957), 961–968.
^ Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.
^ Harary, F., On the reconstruction of a graph from a collection of subgraphs. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52.
^ McKay, B. D., Small graphs are reconstructible, Australas. J. Combin., 15 (1997), 123–126.
^ Bollobás, B., Almost every graph has reconstruction number three, J. Graph Theory, 14 (1990), 1–4.
^ Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory, 1 (1977), 19–25.
^ Kocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B, 42 (1987), 46–63.
^ Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205–236 (1978).