Graphs self-complementary in Kn—e

✍ Scribed by C.R.J. Clapham

• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 467 KB
• Volume: 81
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(90)90062-m

✦ Synopsis

Graphs self-complementary in K,, -e exist for those values of n where self-complementary graphs do not exist. For these graphs, the structure of the complementing permutation is analysed and their diameter is determined.

The definition is related to the notions of "self-complement index" and "self-complementary index" defined by other authors.

Definition.

A graph G that is one of the factors in an isomorphic factorisation of K,, -e into 2 factors is called self -complementary in K,, -e.

Since K,, -e has $z(n -1) -1 edges, such a factorisation is only possible if this number is divisible by 2. Thus it is necessary that n = 2 or 3 (mod 4). We can compare this with the fact that isomorphic factorisations of K,, into 2 factors, i.e. self-complementary graphs, only exist if n = 0 or 1 (mod 4). Graphs selfcomplementary in K,, -e in a sense fill the gap where self-complementary graphs do not exist. In Section 1, we determine the structure of the 'complementing permutation' of such graphs and in Section 2 their diameter is determined. Other authors have defined the notions of "self-complement index" and "selfcomplementary index" and in Sections 3 and 4 these are related to the subject of the present paper.