# Complement of a Cayley graph

Let $X(G,S)$ be the (undirected) Cayley graph, with $G$ group and $S \subseteq G$ such that $1_G \notin S$ and $S=S^{-1}$. Is the complement of $X$ a Cayley graph?

-
It seems to me that the ideal answer to this question has been given (but not accepted). I have voted to close the question as no longer relevant -- I don't think we need to see it popping back up again ad infinitum. – Pete L. Clark May 9 '10 at 8:45

## 1 Answer

The complete graph on $|G|$ vertices is a Cayley graph for $S=G\setminus\{1_G\}$. Its complement, the graph without edges, is not a Cayley graph.

-
Isn't it the Cayley graph (under tbg's defintion) for $S=\emptyset$? – Robin Chapman Apr 25 '10 at 7:00
@Robin Chapman: usually, $S$ is assumed to be a generating set. – Benoît Kloeckner Apr 25 '10 at 8:13
Amongst people who actually work with the things, Cayley graphs are not required to be connected. For example, there is Sabidussi's theorem which asserts that a graph is a Cayley graph for the group $G$ if and only if $G$ acts regularly on its vertices. – Chris Godsil Apr 25 '10 at 18:54
If S is not required to be a generating set, then the answer to the original question is immediately and trivially yes. The partition of G into S and its complement set is mirrored in an obvious way in the partition of the complete graph into X and its complement graph. So requiring S to be a generating set is one possible way of trying to make the question be not so boring, but as my answer shows it still doesn't succeed in doing so. – David Eppstein Apr 25 '10 at 20:06