Reconstruction conjecture
Are graphs uniquely determined by their subgraphs? |
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]}
Formal statements
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:
- Reconstruction Conjecture: Any two hypomorphic graphs on at least three vertices 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 subgraphs are isomorphic.
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.
- Edge Reconstruction Conjecture: (Harary, 1964)^{[3]} Any two graphs with at least four edges and having the same edge-decks are isomorphic.
Verification
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 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.
- Regular graphs^{[6]} - Regular Graphs are reconstructible by direct application of some of the facts that can be recognized from the deck of a graph. Given an -regular graph and its deck , we can recognize that the deck is of a regular graph by recognizing its degree sequence. Let us now examine one member of the deck , . This graph contains some number of vertices with a degree of and vertices with a degree of . We can add a vertex to this graph and then connect it to the vertices of degree to create an -regular graph which is isomorphic to the graph which we started with. Therefore, all regular graphs are reconstructible from their decks. A particular type of regular graph which is interesting is the complete graph.^{[7]}
- Trees^{[6]}
- Disconnected graphs^{[6]}
- Unit interval graphs ^{[8]}
- Separable graphs without end vertices
- Maximal planar graphs
- Maximal outerplanar graphs
- Outerplanar graphs
- Critical blocks
Recognizable properties
{{ safesubst:#invoke:Unsubst||$N=Unreferenced section |date=__DATE__ |$B= {{ safesubst:#invoke:Unsubst||$N=Unreferenced |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }} }}
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:
- Order of the graph – The order of a graph , is recognizable from as the multiset contains each subgraph of created by deleting one vertex of . Hence ^{[7]}
- Number of edges of the graph – The number of edges in a graph with vertices, is recognizable. First note that each edge of occurs in members of . This is true by the definition of which ensures that each edge is included every time that each of the vertices it is incident with is included in a member of , so an edge will occur in every member of except for the two in which its endpoints are deleted. Hence, where is the number of edges in the ith member of ^{[7]}
- Degree sequence – The degree sequence of a graph is recognizable because the degree of every vertex is recognizable. To find the degree of a vertex , we will examine the graph created by deleting it, . This graph contains all of the edges not incident with ,so if is the number of edges in and is the number of edges in , then . If we can tell the degree of every vertex in the graph, we can tell the degree sequence of the graph.^{[7]}
- Tutte polynomial
- Planarity
- The types of spanning trees in a graph
- Chromatic polynomial
- Being a perfect graph or an interval graph, or some other subclasses of perfect graphs ^{[8]}
Reduction
The reconstruction conjecture is true if all 2-connected graphs are reconstructible ^{[9]}
Other structures
It has been shown that the following are not in general reconstructible:
- Digraphs: Infinite families of non-reconstructible digraphs are known, including tournaments (Stockmeyer^{[10]}) and non-tournaments (Stockmeyer^{[11]}). A tournament is reconstructible if it is not strongly connected.^{[12]} A weaker version of the reconstruction conjecture has been conjectured for digraphs, see New digraph reconstruction conjecture.
- Hypergraphs (Kocay^{[13]}).
- Infinite graphs. Let T be a tree on an infinite number of vertices such that every vertex has infinite degree. The counterexample is T and 2T. The question of reconstructibility for locally finite infinite graphs is still open.
See also
Further reading
For further information on this topic, see the survey by Nash-Williams.^{[14]}
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.
- ↑ ^{3.0} ^{3.1} 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.
- ↑ ^{6.0} ^{6.1} ^{6.2} {{#invoke:citation/CS1|citation |CitationClass=citation }}
- ↑ ^{7.0} ^{7.1} ^{7.2} ^{7.3} Template:Cite web
- ↑ ^{8.0} ^{8.1} von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
- ↑ Yang Yongzhi:The reconstruction conjecture is true if all 2-connected graphs are reconstructible. Journal of graph theory 12, 237–243 (1988)
- ↑ Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1 (1977), 19–25.
- ↑ Stockmeyer, P. K., A census of non-reconstructable digraphs, I: six related families, J. Combin. Theory Ser. B 31 (1981), 232–239.
- ↑ Harary, F. and Palmer, E., On the problem of reconstructing a tournament from sub-tournaments, Monatsh. Math. 71 (1967), 14–23.
- ↑ 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).