New digraph reconstruction conjecture

The reconstruction conjecture of Stanisław Ulam is one of the best-known open problems in graph theory.

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.

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

Each vertex in graph 1 matches one from graph 2. In each subgraph made by removing one of the vertices from graph 1, and the matching vertex from graph 2, the outdegree of each remaining vertex in graph 1's subgraph is the same as its matching counterpart in graph 2's subgraph.

This will always be true given graphs 1 and 2 are isomorphic, but the conjecture states that this works in reverse, where knowing only that vertices between two graphs can be paired such that the outdegrees in each subgraph constructed as described match for every vertex is enough information to determine the two graphs are isometric.