Hypomorphy of graphs up to complementation (Q2519016)

For any graph \(G\) and \(K\subseteq V(G)\) let \(G[K]\) denote the subgraph of \(G\) induced by \(K\). It is well-known that if two graphs \(G\) and \(G'\) on the same set of \(n\) vertices are such that \(G[K]\simeq G'[K]\) for all subsets \(K\) of vertices of size \(k\), for some \(2\leq k\leq n-2\), then \(G\) and \(G'\) are identical. In this paper the authors look for similar results if the condition on \(G[K]\) and \(G'[K]\) are relaxed in this fashion. Two graphs on the same set of vertex are said to be isomorphic (equal) up to complementation if \(G\) is isomorphic (equal) to \(G\) or its complement \(\overline{G}\). They are called \(k\)-hypomorphic up to complementation if, for every \(k\)-element subset \(K\) of \(V\), the subgraphs \(G[K]\) and \(G'[K]\) are isomorphic up to complementation. A graph \(G\) is said to be \(k\)-reconstructible up to complementation if every graph \(G'\) which is \(k\)-hypomorphic to \(G\) up to complementation is isomorphic to \(G\) up to complementation. The authors give a partial characterization of the set \(\mathcal S\) of ordered pairs \((n,k)\) such that two graphs on the same set of \(n\) vertices are equal up to complementation when they are \(k\)-hypomorphic up to complementation. In particular they prove that \(\mathcal S\) contains all ordered pairs \((n,k)\) such that \(4 \leq k \leq v-4\) and that \(4\) is the least integer \(k\) such that every graph \(G\) having a large number of vertices is \(k\)-reconstructible up to complementation.