Constructing self-complementary graphs How does one go about systematically constructing a self-complementary graph, on say 8 vertices?
[Added: Maybe everyone else knows this already, but I had to look up my guess to be sure it was correct: a self-complementary graph is a simple graph which is isomorphic to its complement.  --PLC]
 A: Take a complete graph with vertex set $V$ and edge set $E={V\choose2}$. Let $\alpha$ be any permutation of $V$ in which the length of each cycle is a multiple of $4$, except for at most one $1$-cycle. (Of course, such permutations exist if and only if $|V|\equiv 0$ or $1\pmod 4$.)
Let $\beta$ be the permutation of $E$ induced by $\alpha$. Observe that $\beta$ contains only cycles of even length. Color the edges in each cycle alternately black and white. The graph consisting of the black edges is self-complementary.
Example. To construct self-complementary graphs of order $5$, take $V=\{a,b,c,d,e\}$ and let $\alpha=(a\;b\;c\;d)(e)$ so that $\beta=(ab\;bc\;cd\;ad)(ac\;bd)(ae\;be\;\;ce\;de)\;$. If we choose the edges $ab,cd$ and $ac$ (i.e. "color them black") we get a $4$-point path $P_4$. Now we can choose the edges $be,de$ obtaining the self-complementary graph $C_5$, or else we can choose $ae,ce$ obtaining the other self-complementary graph of order $5$, the one that looks like the letter A.
Exercise. Construct all of the self-complementary graphs of order $8$.
A: Systematically is easy; systematically and efficiently, I don't know. It's easy to work out how many edges such a graph must have, that's a start. There's also some information at http://oeis.org/A000171
A: Here's a nice little algorithm for constructing a self-complementary graph from a self-complementary graph $H$ with $4k$ or $4k+1$ vertices, $k = 1, 2, ...$ (e.g., from a self-complementary graph with $4$ vertices, one can construct a self-complementary graph with $8$ vertices; from $5$ vertices, construct one with $9$ vertices).
See this PDF on constructing self-complementary graphs.
A: If you have a self-complementary graph of order 4n, half the vertices must each lie on fewer than 2n edges and the other half must lie on 2n or more edges. Add a vertex by connecting it to the 2n vertices lying on fewer than 2n edges. The result is a self-complementary graph of order 4n+1.
You can create a second self-complementary graph of order 4n+1 by taking the self-complementary graph of order 4n and connecting the new point to the 2n vertices lying on 2n or more edges. 
A: If every prime factor of $n$ is $1\bmod 4$ then there is an easy circulant graph that is self complementary.
What you do is let the vertices be the congruence classes from $0$ to $n-1 \bmod n$ and then you add an edge between two vertices if their difference is a quadratic residue $\bmod p$ for an even number of primes $p$ dividing $n$. (you need $p$ to be $1\bmod 4$ so that it doesn't matter if you take the positive or negative difference).
To see the graph is self complementary you notice that multiplying every vertex by a residue that is a primitive root $\bmod p^k$ for all $p$ is an isomorfism into the complement graph ( or any number that is a non-quadratic residue $\bmod$ every $p$).
