The reconstruction conjecture of Stanisław Ulam is one of the best-known open problems in graph theory. Using the terminology of Frank Harary[1] it can be stated as follows: If G and H are two graphs on at least three vertices and ƒ is a bijection from V(G) to V(H) such that G\{v} and H\{ƒ(v)} are isomorphic for all vertices v in V(G), then G and H are isomorphic.
In 1964 Harary[2] extended the reconstruction conjecture to directed graphs on at least five vertices as the so-called digraph reconstruction conjecture. Many results supporting the digraph reconstruction conjecture appeared between 1964 and 1976. However, this conjecture was proved to be false when P. K. Stockmeyer discovered several infinite families of counterexample pairs of digraphs (including tournaments) of arbitrarily large order.[3][4][5] The falsity of the digraph reconstruction conjecture caused doubt about the reconstruction conjecture itself. Stockmeyer even observed that “perhaps the considerable effort being spent in attempts to prove the (reconstruction) conjecture should be balanced by more serious attempts to construct counterexamples.”[3]
In 1979, Ramachandran revived the digraph reconstruction conjecture in a slightly weaker form called the new digraph reconstruction conjecture. In a digraph, the number of arcs incident from (respectively, to) a vertex v is called the outdegree (indegree) of v and is denoted by od(v) (respectively, id(v)). The new digraph conjecture may be stated as follows:[6][7]
If D and E are any two digraphs and ƒ is a bijection from V(D) to V(E) such that D\{v} and E\{ƒ(v)} are isomorphic and (od(v),id(v)) = (od(ƒ(v)),id(ƒ(v))) for all v in V(D), then D and E are isomorphic.
The new digraph reconstruction conjecture reduces to the reconstruction conjecture in the undirected case, because if all the vertex-deleted subgraphs of two graphs are isomorphic, then the corresponding vertices must have the same degree. Thus, the new digraph reconstruction conjecture is stronger than the reconstruction conjecture, but weaker than the disproved digraph reconstruction conjecture. Several families of digraphs have been shown to satisfy the new digraph reconstruction conjecture and these include all the digraphs in the known counterexample pairs to the digraph reconstruction conjecture.
Reductions
edit- All digraphs are N-reconstructible if all digraphs with 2-connected underlying graphs are N-reconstructible.[8]
- All digraphs are N-reconstructible if and only if either of the following two classes of digraphs are N-reconstructible, where diam(D) and radius(D) are defined to be the diameter and radius of the underlying graph of D.[9]
- Digraphs with diam(D) ≤ 2 or diam(D) = diam(Dc) = 3
- Digraphs D with 2-connected underlying graphs and radius(D) ≤ 2
Present status
editAs of 2024, no counterexample to the new digraph reconstruction conjecture is known. This conjecture is now also known as the degree associated reconstruction conjecture.
References
edit- ^ Harary, Frank (1969), Graph Theory, Reading, Mass.: Addison-Wesley, MR 0256911.
- ^ Harary, Frank (1964), "On the reconstruction of a graph from a collection of subgraphs", in Fiedler, M. (ed.), Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Publ. House Czechoslovak Acad. Sci., Prague, pp. 47–52, MR 0175111
- ^ a b Stockmeyer, Paul K. (1977), "The falsity of the reconstruction conjecture for tournaments", Journal of Graph Theory, 1 (1): 19–25, doi:10.1002/jgt.3190010108, MR 0453584. Erratum, J. Graph Th. 62 (2): 199–200, 2009, doi:10.1002/jgt.20398, MR2555098.
- ^ Stockmeyer, Paul K. (1981), "A census of nonreconstructible digraphs. I. Six related families", Journal of Combinatorial Theory, Series B, 31 (2): 232–239, doi:10.1016/S0095-8956(81)80027-5, MR 0630985.
- ^ Stockmeyer, Paul K. (1991), A census of nonreconstructible digraphs II: A family of tournaments, Preprint.
- ^ Ramachandran, S. (1979), "A digraph reconstruction conjecture", Graph Theory Newsletter, 8 (4), Western Michigan University.
- ^ Ramachandran, S. (1981), "On a new digraph reconstruction conjecture", Journal of Combinatorial Theory, Series B, 31 (2): 143–149, doi:10.1016/S0095-8956(81)80019-6, MR 0630977.
- ^ Ramachandran, S; Monikandan, S (2006), "All Digraphs are N-reconstructible if all Digraphs with 2-connected underlying Graphs are N-reconstructible", Utilitas Mathematica, 71, UTIL MATH PUBL INC: 225–234, MR 2278835
- ^ Ramachandran, S (2012), "Sufficient Conditions For The N-Reconstructibility Of All Digraphs", Utilitas Mathematica, 88, UTIL MATH PUBL INC: 183–188, MR 2975831