MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.