English Wikipedia @ Freddythechick

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

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

Given a graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V,E)} , a vertex-deleted subgraph of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} is a subgraph formed by deleting exactly one vertex from  . By definition, it is an induced subgraph of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} .

For a graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} , the deck of G, denoted Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} , is the multiset of isomorphism classes of all vertex-deleted subgraphs of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} . Each graph in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V,E)} , an edge-deleted subgraph of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} is a subgraph formed by deleting exactly one edge from  .

For a graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} , the edge-deck of G, denoted Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ED(G)} , is the multiset of all isomorphism classes of edge-deleted subgraphs of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} . Each graph in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ED(G)} 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |V(G)|} is recognizable from   as the multiset Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} contains each subgraph of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} created by deleting one vertex of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} . Hence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |V(G)| = |D(G)|} [5]
  • Number of edges of the graph – The number of edges in a graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} vertices, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |E(G)|} is recognizable. First note that each edge of   occurs in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-2} members of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} . This is true by the definition of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} which ensures that each edge is included every time that each of the vertices it is incident with is included in a member of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} , so an edge will occur in every member of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} except for the two in which its endpoints are deleted. Hence, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |E(G)| = \sum \frac{q_i}{n-2}} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_i} is the number of edges in the ith member of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} .[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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i} —the vertex absent from the ith member of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} —, we will examine the graph created by deleting it, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_i} . This graph contains all of the edges not incident with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i} , so if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_i} is the number of edges in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_i} , 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -vertex-connected when deleting any vertex creates a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} -vertex-connected graph; thus, if every card is a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} -vertex-connected graph, we know the original graph was Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -vertex-connected. We can also determine if the original graph was connected, as this is equivalent to having any two of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_i} being connected.[5]
  • Tutte polynomial
  • Characteristic 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 13 vertices by Brendan McKay.[7][8]

In a probabilistic sense, it has been shown by Béla Bollobás that almost all graphs are reconstructible.[9] This means that the probability that a randomly chosen graph on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} vertices is not reconstructible goes to 0 as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.

Reconstructible graph families

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

  • Regular graphs[10] - 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} and its deck Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} , 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_i} . This graph contains some number of vertices with a degree of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} vertices with a degree of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} . We can add a vertex to this graph and then connect it to the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} vertices of degree Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} to create an Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -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[10]
  • Disconnected graphs[10]
  • Unit interval graphs [6]
  • Separable graphs without end vertices[11]
  • Maximal planar graphs
  • Maximal outerplanar graphs
  • Outerplanar graphs
  • Critical blocks

Reduction

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

Duality

The vertex reconstruction conjecture obeys the duality that if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} can be reconstructed from its vertex deck Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} , then its complement Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G'} can be reconstructed from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G')} as follows: Start with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G')} , take the complement of every card in it to get Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(G)} , use this to reconstruct Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} , then take the complement again to get Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G'} .

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[13]) and non-tournaments (Stockmeyer[14]). A tournament is reconstructible if it is not strongly connected.[15] A weaker version of the reconstruction conjecture has been conjectured for digraphs, see new digraph reconstruction conjecture.
  • Hypergraphs (Kocay[16]).
  • Infinite graphs. If T is the tree where every vertex has countably infinite degree, then the union of two disjoint copies of T is hypomorphic, but not isomorphic, to T.[17]
  • Locally finite graphs, which are graphs where every vertex has finite degree. 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.[18]

See also

Further reading

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

References

  1. ^ Kelly, P. J., A congruence theorem for trees, Pacific J. Math. 7 (1957), 961–968.
  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 (1): 35–43. doi:10.2307/2316851. JSTOR 2316851.
  4. ^ 4.0 4.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.
  5. ^ 5.0 5.1 5.2 5.3 5.4 Wall, Nicole. "The Reconstruction Conjecture" (PDF). Retrieved 2014-03-31.
  6. ^ 6.0 6.1 von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
  7. ^ McKay, B. D., Small graphs are reconstructible, Australas. J. Combin. 15 (1997), 123–126.
  8. ^ McKay, Brendan (2022). "Reconstruction of Small Graphs and Digraphs". Austras. J. Combin. 83: 448–457.
  9. ^ Bollobás, B., Almost every graph has reconstruction number three, J. Graph Theory 14 (1990), 1–4.
  10. ^ 10.0 10.1 10.2 Harary, F. (1974), "A survey of the reconstruction conjecture", Graphs and Combinatorics, Lecture Notes in Mathematics, vol. 406, Springer, pp. 18–28, doi:10.1007/BFb0066431, ISBN 978-3-540-06854-9
  11. ^ Bondy, J.-A. (1969). "On Ulam's conjecture for separable graphs". Pacific J. Math. 31 (2): 281–288. doi:10.2140/pjm.1969.31.281.
  12. ^ Yang Yongzhi:The reconstruction conjecture is true if all 2-connected graphs are reconstructible. Journal of graph theory 12, 237–243 (1988)
  13. ^ Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1 (1977), 19–25.
  14. ^ Stockmeyer, P. K., A census of non-reconstructable digraphs, I: six related families, J. Combin. Theory Ser. B 31 (1981), 232–239.
  15. ^ Harary, F. and Palmer, E., On the problem of reconstructing a tournament from sub-tournaments, Monatsh. Math. 71 (1967), 14–23.
  16. ^ Kocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B 42 (1987), 46–63.
  17. ^ Nash-Williams, C. St. J. A.; Hemminger, Robert (3 December 1991). "Reconstruction of infinite graphs" (PDF). Discrete Mathematics. 95 (1): 221–229. doi:10.1016/0012-365X(91)90338-3.
  18. ^ 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
  19. ^ Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205–236 (1978).
Retrieved from "https://enwiki.freddythechick.net/index.php?title=Reconstruction_conjecture&oldid=14354862"