A property of most of the known non-reconstructible digraphs
S. Ramachandran · AKCE International Journal of Graphs and Combinatorics · 2022
For a graph/digraph G, the multiset {G–v| v∈V(G)} is called the deck (Deck(G)) and its members, the cards of G. If H has the same deck as G, it is called a hypomorph of G. Reconstruction conjecture (RC) (Ulam, 1960) claims that all hypomorphic graphs are isomorphic. Graphs/digraphs that satisfy RC are called reconstructible. Intersection of two cards in a hypomorph of G is “defined” as a pasting of them. RC is open whereas there are ten infinite families of pairs (Xp, Xp*) of non-reconstructible digraphs. For nine of them we prove the following. 1. Deck(Xp) has a pair of cards such that all their pastings in hypomorphs of Xp are isomorphic. 2. Xp* is the only nonisomorphic hypomorph of Xp and vice versa. 3. For the exceptional family, Deck(Xp) has no pair of cards with all their pastings as members of Deck(Xp) isomorphic and the existence of a digraph other than Xp and Xp* with Deck(Xp) as its deck is possible. An attempt to prove an extension of RC to digraphs which claims that “all digraphs G are reconstructible from the collection {(G–v, (od(v),id(v)))| v∈V(G)}” using the method of contradiction has to start from the existing non-reconstructible digraph pairs.