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