In graph theory, informally, the reconstruction conjecture says that graphss are determined uniquely by their subgraphs. It is due to Kelly and Ulam.

Formal statements

, a vertex-deleted subgraph is a subgraph. By definition, it is an induced subgraph.

, the deck of G, is the multiset 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 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.

, an edge-deleted subgraph is a subgraph.

, the edge-deck of G, is the multiset is called an edge-card.

• Edge Reconstruction Conjecture: (Harary, 1964) 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

• Number of edges of the graph is the number of edges in the i.

• th card.

• Degree sequence—the vertex absent from the i. If we can tell the degree of every vertex in the graph, we can tell the degree sequence of the graph.

• (Vertex-)Connectivity being connected.

• Tutte polynomial

• Characteristic polynomial

• Planarity

• The number of spanning treess in a graph

• Chromatic polynomial

• Being a perfect graph or an interval graph, or certain other subclasses of perfect graphs

Verification

Both the reconstruction and set reconstruction conjectures have been verified for all graphs with at most 13 vertices by Brendan McKay.

In a probabilistic sense, it has been shown by Béla Bollobás that almost all graphs are reconstructible. 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-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.

• Trees

• Disconnected graphs

• Unit interval graphs

• Separable graphs without end vertices

• Maximal planar graphs

• Maximal outerplanar graphs

• Outerplanar graphs

• Critical blocks

Reduction

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

Duality

.

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) and non-tournaments (Stockmeyer). A tournament is reconstructible if it is not strongly connected. A weaker version of the reconstruction conjecture has been conjectured for digraphs, see new digraph reconstruction conjecture.

• Hypergraphs, including all k-uniform hypergraphs for k>2 (Kocay).

• 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.(Fisher)

• 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.

See also

• New digraph reconstruction conjecture

• Partial symmetry

Further reading

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

References