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][3]
Unsolved problem in mathematics: Are graphs uniquely determined by their subgraphs? (more unsolved problems in mathematics) |
Formal statements
Given a graph , a vertex-deleted subgraph of is a subgraph formed by deleting exactly one vertex from . By definition, it is an induced subgraph of .
For a graph , the deck of G, denoted , is the multiset of isomorphism classes 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[4] 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 isomorphism classes of edge-deleted subgraphs of . Each graph in is called an edge-card.
- Edge Reconstruction Conjecture: (Harary, 1964)[4] Any two graphs with at least four edges and having the same edge-decks are isomorphic.
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:
- 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 [5]
- 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 [5]
- 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.[5]
- (Vertex-)Connectivity – By definition, a graph is -vertex-connected when deleting any vertex creates a -vertex-connected graph; thus, if every card has a -vertex-connected graph, we know the original graph was -vertex-connected. We can also determine if the original graph was connected, as this is equivalent to having any two of the being connected.[5]
- Tutte polynomial
- Planarity
- The types of spanning trees in a graph
- Chromatic polynomial
- Being a perfect graph or an interval graph, or certain other subclasses of perfect graphs [6]
Verification
Both the reconstruction and set reconstruction conjectures have been verified for all graphs with at most 11 vertices by Brendan McKay.[7]
In a probabilistic sense, it has been shown by Béla Bollobás that almost all graphs are reconstructible.[8] 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).
- Regular graphs[9] - 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.[5]
- Trees[9]
- Disconnected graphs[9]
- Unit interval graphs [6]
- Separable graphs without end vertices[10]
- Maximal planar graphs
- Maximal outerplanar graphs
- Outerplanar graphs
- Critical blocks
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:
- Digraphs: Infinite families of non-reconstructible digraphs are known, including tournaments (Stockmeyer[12]) and non-tournaments (Stockmeyer[13]). A tournament is reconstructible if it is not strongly connected.[14] A weaker version of the reconstruction conjecture has been conjectured for digraphs, see new digraph reconstruction conjecture.
- Hypergraphs (Kocay[15]).
- Infinite graphs. Let T be a tree on an infinite number of vertices such that every vertex has infinite degree, and let nT be the disjoint union of n copies of T. These graphs are hypomorphic, and thus not reconstructible. Every vertex-deleted subgraph of any of these graphs is isomorphic: they all are the disjoint union of an infinite number of copies of T.
- Locally finite graphs. The question of reconstructibility for locally finite infinite trees (the Harary-Schwenk-Scott conjecture from 1972) was a longstanding open problem until 2017, when a non-reconstructible tree of maximum degree 3 was found by Bowler et al.[16]
See also
- New digraph reconstruction conjecture
- Partial symmetry
Further reading
For further information on this topic, see the survey by Nash-Williams.[17]
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.
- O'Neil, Peter V. (1970). "Ulam's conjecture and graph reconstructions". Amer. Math. Monthly. 77: 35–43. doi:10.2307/2316851.
- 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.
- Wall, Nicole. "The Reconstruction Conjecture" (PDF). Retrieved 2014-03-31.
- von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
- 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.
- 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
- Bondy, J.-A. (1969). "On Ulam's conjecture for separable graphs". Pacific J. Math. 31: 281–288. doi:10.2140/pjm.1969.31.281.
- 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.
- Bowler, N., Erde, J., Heinig, P., Lehner, F. and Pitz, M. (2017), A counterexample to the reconstruction conjecture for locally finite trees. Bull. London Math. Soc.. doi:10.1112/blms.12053
- Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205–236 (1978).