Reconstruction conjecture

Reconstruction conjecture

Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to KellyKelly, P. J., [http://projecteuclid.org/getRecord?id=euclid.pjm/1103043674 A congruence theorem for trees] , Pacific J. Math., 7 (1957), 961–968.] and UlamUlam, S. M., A collection of mathematical problems, Wiley, New York, 1960.] .

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

HararyHarary, 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.] 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 (McKayMcKay, B. D., Small graphs are reconstructible, Australas. J. Combin., 15 (1997), 123–126.] ).

In a probabilistic sense, it has been shown (BollobásBollobás, B., Almost every graph has reconstruction number three, J. Graph Theory, 14 (1990), 1–4.] ) 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.

Other structures

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

* Digraphs (StockmeyerStockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory, 1 (1977), 19–25.] )
* Hypergraphs ( KocayKocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B, 42 (1987), 46–63.] )
* Infinite graphs

Further reading

For further information on this topic, see the survey by Nash-WilliamsNash-Williams, C. St. J. A., The Reconstruction Problem, in "Selected topics in graph theory", 205–236 (1978).] .

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • New digraph reconstruction conjecture — Unsolved problems in mathematics Are digraphs uniquely determined by their subgraphs? The reconstruction conjecture of Stanislaw Ulam is one of the best known open problems in graph theory. Using the terminology of Frank Harary[1] it can be… …   Wikipedia

  • Reconstruction — NOTOC Reconstruction may refer to:Politics, history and sociology*Postwar reconstruction. **Reconstruction era of the United States, the period between 1865 to 1877 when the US government focused on resolving the consequences and aftermath of the …   Wikipedia

  • Conjecture — For text reconstruction, see Conjecture (textual criticism). A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term conjecture in scientific philosophy.… …   Wikipedia

  • Conjecture (textual criticism) — For unproven proposition, see Conjecture. Conjecture (conjectural emendation) is a critical reconstruction of the original reading of a clearly corrupt, contaminated, nonsensical or illegible textual fragment. Conjecture is one of the techniques… …   Wikipedia

  • Lovász conjecture — In graph theory, the Lovász conjecture (1970) is a classical problem on Hamiltonian paths in graphs. It says:: Every finite connected vertex transitive graph contains a Hamiltonian path .The original article of Lovász stated the result in the… …   Wikipedia

  • Liste de conjectures mathématiques — Ce qui suit est une liste de conjectures mathématiques, non exhaustive. Elles sont divisées en quatre sections, en accord avec leur état en 2011. Voir aussi : Conjecture d Erdős (en), qui liste des conjectures de Paul Erdős et de ses… …   Wikipédia en Français

  • List of unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Contents 1 Millennium Prize Problems 2 Other still unsolved problems 2.1 Additive number theory …   Wikipedia

  • Problèmes non résolus en mathématiques — Ce qui suit est une liste de problèmes non résolus en mathématiques. Sommaire 1 Problèmes du prix du millénaire 2 Autres problèmes encore non résolus 2.1 Théorie des nombres 2.2 …   Wikipédia en Français

  • List of conjectures — This is an incomplete list of mathematical conjectures. They are divided into four sections, according to their status in 2007. See also: * Erdős conjecture, which lists conjectures of Paul Erdős and his collaborators * Unsolved problems in… …   Wikipedia

  • Crispin Nash-Williams — Naissance 19 décembre 1932 Cardiff, Pays de Galles Décès 20 janvier 2001 (à 68 ans) Ascot, Berkshire Nationalité anglaise Champs …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”