Reconstruction conjecture

From Wikinfo

Search for "Reconstruction_conjecture" on Wikipedia  • Wikimedia Commons • Wiktionary • Wikiquote • Wikibooks • Mediawiki Wikia • Wikitravel • Google Advanced Search • Yahoo Advanced Search • WorldCat Advanced Search • Amazon • Recent NY Times • Older NY Times.

For criticism see Criticism of Reconstruction_conjecture

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].

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

Formal statement

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

For a graph <math>G</math>, the deck of G, denoted <math>D(G)</math>, is the collection of all vertex-deleted subgraphs of <math>G</math>. 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 <math>D(G)</math> 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.

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 <math>n</math> vertices is not reconstructible goes to 0 as <math>n</math> 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.

Other structures

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

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

Further reading

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

References

1. ^ Kelly, P. J., A congruence theorem for trees, Pacific J. Math., 7 (1957), 961–968.
2. ^ Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.
3. ^ 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.
4. ^ McKay, B. D., Small graphs are reconstructible, Australas. J. Combin., 15 (1997), 123–126.
5. ^ Bollobás, B., Almost every graph has reconstruction number three, J. Graph Theory, 14 (1990), 1–4.
6. ^ Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory, 1 (1977), 19–25.
7. ^ Kocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B, 42 (1987), 46–63.
8. ^ Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205–236 (1978).

This page uses content from Wikipedia. The original article was at Reconstruction conjecture. The list of authors can be seen in the page history. The text of this Wikinfo article is available under the GNU Free Documentation License and the Creative Commons Attribution-Share Alike 3.0 license. English | Română | edit