New digraph reconstruction conjecture

Unsolved problems in mathematics

Are digraphs uniquely determined by their subgraphs?

The reconstruction conjecture of Stanislaw 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)).

New digraph reconstruction conjecture

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.^[6][7]

The new digraph reconstruction conjecture reduces to the reconstruction conjecture in the undirected case, because if 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. As of 2008, no counterexample to the new digraph reconstruction conjecture is known.

References

1. ^ Harary, Frank (1969), Graph Theory, Reading, Mass.: Addison-Wesley, MR0256911 .
2. ^ Harary, Frank (1964), "On the reconstruction of a graph from a collection of subgraphs", in Fiedler, M., Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Publ. House Czechoslovak Acad. Sci., Prague, pp. 47–52, MR0175111 
3. ^ ^{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, MR0453584 . Erratum, J. Graph Th. 62 (2): 199–200, 2009, doi:10.1002/jgt.20398, MR2555098.
4. ^ 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, MR630985 .
5. ^ Stockmeyer, Paul K. (1991), A census of nonreconstructible digraphs II: A family of tournaments, Preprint .
6. ^ Ramachandran, S. (1979), "A digraph reconstruction conjecture", Graph Theory Newsletter (Western Michigan University) 8 (4) .
7. ^ 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, MR630977 .