Boolean sum of graphs and reconstruction up to complementation
Jamel Dammak, Gérard Lopez, Maurice Pouzet, Hamza Si Kaddour · Advances in Pure and Applied Mathematics · 2013
Let V be a set of cardinality v (possibly infinite). Two graphs G and with vertex set V are isomorphic up to complementation if is isomorphic to G or to the complement of G . Let k be a non-negative integer. The graphs G and are k -hypomorphic up to complementation if for every k -element subset K of V , the induced subgraphs and are isomorphic up to complementation. A graph G is k -reconstructible up to complementation if every graph which is k -hypomorphic to G up to complementation is in fact isomorphic to G up to complementation. We prove that a graph G has this property provided that . Moreover, under these conditions, if or , then G and are the only graphs k -hypomorphic to G up to complementation. A description of pairs of graphs with the same 3-homogeneous subsets is a key ingredient in our proof.