Timeline for Complement of a Cayley graph
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 25, 2010 at 20:06 | comment | added | David Eppstein | 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. | |
| Apr 25, 2010 at 18:54 | comment | added | Chris Godsil | 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. | |
| Apr 25, 2010 at 8:13 | comment | added | Benoît Kloeckner | @Robin Chapman: usually, $S$ is assumed to be a generating set. | |
| Apr 25, 2010 at 7:00 | comment | added | Robin Chapman | Isn't it the Cayley graph (under tbg's defintion) for $S=\emptyset$? | |
| Apr 25, 2010 at 5:55 | history | answered | David Eppstein | CC BY-SA 2.5 |