Welcome to MathOverflow

Question

0

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?

edited Apr 25 2010 at 6:16

asked Apr 25 2010 at 5:51

tbg
1●1

1

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 2010 at 8:45

David Eppstein · Answer 1 · 2010-04-25 05:55:37Z UTC

2

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.

answered Apr 25 2010 at 5:55

David Eppstein
9,233●1●21●41

	Isn't it the Cayley graph (under tbg's defintion) for $S=\emptyset$? – Robin Chapman Apr 25 2010 at 7:00
	@Robin Chapman: usually, $S$ is assumed to be a generating set. – Benoît Kloeckner Apr 25 2010 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 2010 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 2010 at 20:06

Complement of a Cayley graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.