Properties of non-reconstructible graphs and digraphs

Abstract

Graphs/digraphs G and G′ are hypomorphic (or G′ is a hypomorph of G) if there is a bijection φ V(G) → V(G′) such that G-u ≅ G′-φ(u), for all u ϵ V(G). Such a mapping φ is called a hypomorphism. It is called a dahypomorphism (or G′ is a da-hypomorph of G) if in addition, deg(u) = deg(φ(u)) (when G and G′ are graphs) and (d⁺(u), d^-(u)) = (d⁺(φ(u)), d^-(φ(u))) (when G and G′ are digraphs) for all u ϵ V(G) where d⁺(u) (d∼(u)) is the number of arcs with tail (head) u. A hypomorphism between graphs is a da-hypomorphism. A graph/digraph is called reconstructible (da-reconstructible) if it is isomorphic to all its hypomorphs (da-hypomorphs). Kocay [JCTB 44(1988) 187-200] has studied the properties of non-reconstructible graphs and digraphs through the isomorphisms G-u ≠ G′-φ(u). We do it for non-da-reconstructible digraphs and show that non-da-reconstructible graphs and digraphs behave alike whereas non-reconstructible digraphs behave differently. We also identify a property of graph hypomorphism (in Kocay's theory) which digraph hypomorphism does not have. Such properties have the potential of being used in the final proof (if ever found) that all graphs are reconstructible.