Graph Theory question

deathronan

Hi can anyone help with this exam question....

A (p, q) graph G is said to be self complementary if G is isomorphic to G

(a) Prove that if G is a self-complementary (p, q) graph, p is of the form 4k or 4k+1

(b) Find examples of self-complementary graphs of order 8 and 9.

MathsManiac

I think you left out a "prime" symbol there: (G is to be isomorphic to G').

First part: G and G' together give the complete graph of order p, which has pC2 = p(p-1)/2 edges. So, if G is isomorphic to G', G must have p(p-1)/4 edges. Since one of p and (p-1) must be odd, then the even one must be divisible by 4.

Second part: can't see an obvious way to do it, but messing around in some systematic way with graphs with 8 vertices and 14 edges must be the key. The problem is how to mess about in a sufficiently insightful manner! (Similarly for 9 vertices and 18 edges.)

The following link indicates that there are 10 distinct answers in the case of (8,14) and 36 in the case of (9,18): http://www.research.att.com/~njas/sequences/A000171

deathronan

Cheers mate, appreciate it!