Hypomorphy of graphs up to complementation

AbstractLet V be a set of cardinality v (possibly infinite). Two graphs G and G′ with vertex set V are isomorphic up to complementation if G′ is isomorphic to G or to the complement G¯ of G. Let k be a non-negative integer, G and G′ are k-hypomorphic up to complementation if for every k-element subset K of V, the induced subgraphs G↾K and G↾K′ are isomorphic up to complementation. A graph G is k-reconstructible up to complementation if every graph G′ which is k-hypomorphic to G up to complementation is in fact isomorphic to G up to complementation. We give a partial characterisation of the set S of ordered pairs (n,k) such that two graphs G and G′ on the same set of n vertices are equal up to complementation whenever they are k-hypomorphic up to complementation. We prove in particular that S contains all ordered pairs (n,k) such that 4⩽k⩽n−4. We also prove that 4 is the least integer k such that every graph G having a large number n of vertices is k-reconstructible up to complementation; this answers a question raised by P. Ille [P. Ille, Personal communication, September 2000]