Reconstruction conjecture

Unsolved problem in mathematics:
Are graphs uniquely determined by their subgraphs?
(more unsolved problems in mathematics)

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][3]

Formal statements

graph and the associated deck of single-vertex-deleted subgraphs. Note some of the cards show isomorphic graphs.

Given a graph , a vertex-deleted subgraph of is a subgraph formed by deleting exactly one vertex from . Clearly, it is an induced subgraph of .

For a graph , the deck of G, denoted , is the multiset of all vertex-deleted subgraphs of . Each graph in is called a card. Two graphs that have the same deck are said to be hypomorphic.

With these definitions, the conjecture can be stated as:

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

Harary[4] suggested a stronger version of the conjecture:

Given a graph , an edge-deleted subgraph of is a subgraph formed by deleting exactly one edge from .

For a graph , the edge-deck of G, denoted , is the multiset of all edge-deleted subgraphs of . Each graph in is called an edge-card.

Verification

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

In a probabilistic sense, it has been shown (Bollobás[6]) that almost all graphs are reconstructible. This means that the probability that a randomly chosen graph on vertices is not reconstructible goes to 0 as 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.

Reconstructible graph families

The conjecture has been verified for a number of infinite classes of graphs (and, trivially, their complements).

Recognizable properties

In context of the reconstruction conjecture, a graph property is called recognizable if one can determine the property from the deck of a graph. The following properties of graphs are recognizable:

Reduction

The reconstruction conjecture is true if all 2-connected graphs are reconstructible [11]

Duality

The vertex reconstruction conjecture obeys the duality that if can be reconstructed from its vertex deck , then its complement can be reconstructed from as follows: Start with , take the complement of every card in it to get , use this to reconstruct , then take the complement again to get .

Edge reconstruction does not obey any such duality: Indeed, for some classes of edge-reconstructible graphs it is not known if their complements are edge reconstructible.

Other structures

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

See also

Further reading

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

References

  1. Kelly, P. J., A congruence theorem for trees, Pacific J. Math. 7 (1957), 961968.
  2. Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.
  3. O'Neil, Peter V. (1970). "Ulam's conjecture and graph reconstructions". Amer. Math. Monthly. 77: 35–43. doi:10.2307/2316851.
  4. 1 2 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.
  5. McKay, B. D., Small graphs are reconstructible, Australas. J. Combin. 15 (1997), 123126.
  6. Bollobás, B., Almost every graph has reconstruction number three, J. Graph Theory 14 (1990), 14.
  7. 1 2 3 Harary, F. (1974), "A survey of the reconstruction conjecture", A survey of the reconstruction conjecture, Graphs and Combinatorics. Lecture Notes in Mathematics, 406, Springer, pp. 18–28, doi:10.1007/BFb0066431
  8. 1 2 3 4 Wall, Nicole. "The Reconstruction Conjecture" (PDF). Retrieved 2014-03-31.
  9. 1 2 von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
  10. Bondy, J.-A. (1969). "On Ulam's conjecture for separable graphs". Pacific J. Math. 31: 281–288. doi:10.2140/pjm.1969.31.281.
  11. Yang Yongzhi:The reconstruction conjecture is true if all 2-connected graphs are reconstructible. Journal of graph theory 12, 237–243 (1988)
  12. Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1 (1977), 1925.
  13. Stockmeyer, P. K., A census of non-reconstructable digraphs, I: six related families, J. Combin. Theory Ser. B 31 (1981), 232239.
  14. Harary, F. and Palmer, E., On the problem of reconstructing a tournament from sub-tournaments, Monatsh. Math. 71 (1967), 1423.
  15. Kocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B 42 (1987), 4663.
  16. Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205236 (1978).
This article is issued from Wikipedia - version of the 11/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.