Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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]

share|improve this question
add comment

4 Answers 4

up vote 10 down vote accepted

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.

share|improve this answer
    
This is a beautiful algorithm, thank you. –  John May 23 '11 at 0:40
    
@John, so all you wanted was one self-complementary graph of each (possible) order? I thought you wanted all of them! –  Gerry Myerson May 23 '11 at 2:31
    
@Gerry Yikes: that would certainly be an "efficiency" challenge, indeed! I came across a "comprehensive" "manual" on self-complementary graphs (200+ pages)...but intriguing from what I gleaned. I'll link it in my answer above. –  amWhy May 23 '11 at 2:40
    
@Gerry, I looked at my question again and I agree, my original wording was vague. I've edited the question slightly to reflect on what I meant. –  John May 23 '11 at 3:45
add comment

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.

share|improve this answer
add comment

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. (Needless to say

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$.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.