The (≤5)-hypomorphy of digraphs up to complementation

Abstract

Two digraphs G=(V,E)and G′=(V,E′)are isomorphic up to complementation if G′is isomorphic to G or to the complement G¯≔(V,{(x,y)∈V2:x≠y,(x,y)∉E})of G. The Boolean sum G+̇G′is the symmetric digraph U=(V,E(U))defined by {x,y}∈E(U)if and only if (x,y)∈E and (x,y)∉E′, or (x,y)∉E and (x,y)∈E′. Let k be a nonnegative integer. The digraphs G and G′are (≤k)-hypomorphic up to complementation if for every t-element subset X of V, with t≤k, the induced subdigraphs G↾Xand G↾X′are isomorphic up to complementation. The digraphs G and G′are hereditarily isomorphic (resp. hereditarily isomorphic up to complementation) if for each subset X of V, the induced subdigraphs G↾Xand G↾X′are isomorphic (resp. isomorphic up to complementation). Here, we give the form of the pair {G,G′}whenever G and G′are two digraphs, (≤5)-hypomorphic up to complementation and such that the Boolean sum U≔G+̇G′and the complement U¯are both connected, and thus we deduce that G and G′are hereditarily isomorphic up to complementation; we prove also that the value 5 is optimal. The case U or U¯is not connected is studied in a forthcoming paper. Keywords: Digraph, Isomorphism, k-hypomorphy up to complementation, Hereditary isomorphy up to complementation, Boolean sum, Symmetric digraph, Tournament, Indecomposability