Tell me more ×
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.
up vote 2 down vote favorite

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

2 Answers

up vote 6 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
up vote 2 down vote

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

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.