A property of most of the known non-reconstructible digraphs. Issue 1 (2nd January 2022)

• Record Type: Journal Article
• Authors: Ramachandran, S.
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 19:Issue 1(2022)
• Page Start: 41
• Page End: 48
• Publication Date: 2022-01-02
• Subjects: digraph -- card -- pasting -- isomorphic pastings -- unique non-isomorphic hypomorph; 05C60 -- 05C20
• DOI: 10.1080/09728600.2022.2057259
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: 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.