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?
1
-
1$\begingroup$ 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. $\endgroup$– Pete L. ClarkCommented May 9, 2010 at 8:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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
-
$\begingroup$ Isn't it the Cayley graph (under tbg's defintion) for $S=\emptyset$? $\endgroup$ Commented Apr 25, 2010 at 7:00
-
$\begingroup$ @Robin Chapman: usually, $S$ is assumed to be a generating set. $\endgroup$ Commented Apr 25, 2010 at 8:13
-
$\begingroup$ 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. $\endgroup$ Commented Apr 25, 2010 at 18:54
-
$\begingroup$ 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. $\endgroup$ Commented Apr 25, 2010 at 20:06