Hypomorphy of graphs up to complementation

Abstract

Let $V$ be a set of cardinality $v$ (possibly infinite). Two graphs $G$ and $G^{\prime }$ with vertex set $V$ are {\it isomorphic up to complementation} if $G^{\prime }$ is isomorphic to $G$ or to the complement $\bar{G}$ of $G$. Let $k$ be a non-negative integer, $G$ and $G^{\prime }$ are {\it $k$-hypomorphic up to complementation} if for every $k$-element subset $K$ of $V$, the induced subgraphs $G\_\upharpoonright K$ and $G^{\prime }\_\upharpoonright K$ are isomorphic up to complementation. A graph $G$ is {\it $k$-reconstructible up to complementation} if every graph $G^{\prime }$ 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 $\mathcal{S}$ of pairs $(n,k)$ such that two graphs $G$ and $G^{\prime }$ 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 $\mathcal{S}$ contains all pairs $(n,k)$ such that $4\le k\le 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