All Self-Complementary Symmetric Graphs

✍ Scribed by Wojciech Peisert

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 153 KB
• Volume: 240
• Category: Article
• ISSN: 0021-8693
• DOI: 10.1006/jabr.2000.8714

✦ Synopsis

In 1992, H. Zhang (J. Graph Theory 16, 1-5), using the classification of finite simple groups, gave an algebraic characterisation of self-complementary symmetric graphs. Yet, from this characterisation it does not follow whether such graphs, other than the well-known Paley graphs, exist. In this paper we give a full description of self-complementary symmetric graphs and their automorphism groups. In particular, we prove that apart from the Paley graphs there is another infinite family of selfcomplementary symmetric graphs and, in addition, one more graph not belonging to any of these families. We obtain this by investigating automorphism groups of graphs and applying classification results on primitive permutation groups of low rank. We prove also that the automorphism group of a self-complementary symmetric graph is permutation isomorphic to a subgroup of A L 1 p r with three exceptions, when it can be presented as a subgroup of A L 2 p r .