Does every self-complementary graph has a non-trivial automorphism group?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Every self-complementary graph on more than one vertex has non-trivial automorphisms. See for example page 16 in http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf
Edit: I should add that this result is not too hard to prove, so I give an outline. Suppose $A$ and $B$ are the adjacency matrices of $G$ and its complement. Since $G$ is self-complementary, there is a permutation matrix $P$ such that $P^TAP=B$. Now if $J$ is the all-ones matrix then $B=J-I-A$ and $P^TJP=J$, so we find that $(P^2)^TAP^2=A$. This implies that $P^2$ represents an automorphism of $G$. The trick is to show that $P^2\ne I$, and to show this you need to show that $P$ does not have a cycle of length two.