Reconstruction conjecture
Encyclopedia : R : RE : REC : Reconstruction conjecture
Informally, the reconstruction conjecture in graph theory suggests that a graph is determined uniquely by it's sub-structures.
Definitions
Given a set [X], let [[X]^k] denote the set of all unordered [k-] subsets of [X].
A graph [G] is an ordered pair [(V,E)] where [V] is a set and [E \subset [V]^2]. [H = (V', E')] is called a subgraph of [G = (V,E)] if [V' \subset V], and [E' \subset E \cap [V']^2].
Given a graph [G = (V,E)], a vertex-deleted subgraph of [G] is a subgraph of [G] with formed by deleting exactly one vertex from [G], and every edge attached to it.
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.
Formal statement
Given the above definitions, the Graph Reconstruction Conjecture can be stated as follows:
Reconstruction Conjecture If any two graphs [G] and [H] with at least three vertices have the same deck (i.e. [D(G) = D(H)]), then [G] is isomorphic to [H].
This can also be restated without the definitions above as follows, where [G-v] denotes the vertex-deleted subgraph of [G] formed by deleting [v].
Reconstruction Conjecture Let [G] and [H] be finite graphs with at least three vertices, and let there be a bijection [\sigma:V(G) \rightarrow V(H)] such that [G-v] is isomorphic to [H-\sigma(v)] for every [v \in V(G)]. Then [G] and [H] are isomorphic.
Requirement of 3 vertices
For graphs on two vertices this fails. Indeed, there are exactly two graphs on two vertices (the single edge and two isolated vertices), and they both have the same deck, namely two cards, each exactly a single isolated vertex.
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).
The conjecture has been verified for all graphs with at most 10 vertices (approximately 12.3 million graphs)McMullen, B., Graph Reconstruction Numbers, Master’s Project Report, Rochester Institute of Technology (2005)., and for many classes of graphs on 11 vertices.
In a probabilistic sense, it has been shown (Bollobas, 1990) 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. It was shown that 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, 1977/1981)
- Hypergraphs (Kocay, 1987)
- 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).. One resource on current computational verification of this conjecture is found in McMullen's paper on graph reconstruction numbers.
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.References
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.