SELF-COMPLEMENTARY VERTEX-TRANSITIVE GRAPHS
G.V.V. Jagannadha Rao · Bulletin of the Australian Mathematical Society · 2016
A graph is self-complementary if its complement is isomorphic to the graph itself.A graph is vertex-transitive if its full automorphism group is transitive on its vertex set.This dissertation is intended to present our research results on self-complementary vertex-transitive graphs.In particular, we studied the following problems: constructions of self-complementary vertex-transitive graphs, self-complementary vertex-transitive graphs of order a product of two primes, selfcomplementary metacirculants and self-complementary vertex-transitive graphs of prime-cubed order.The main analysis on these problems relies on two pivotal results due to Guralnick et al. [1] and Li and Praeger [2], which characterise the full automorphism group of a self-complementary vertex-transitive graph in the primitive and the imprimitive cases, respectively.For constructions of self-complementary vertex-transitive graphs, there are generally three known methods: construction by partitioning the complementing isomorphism orbits, construction using the coset graphs and the lexicographic product.In this dissertation we developed various alternative construction methods.As a result, we find a family of self-complementary Cayley graphs of non-nilpotent groups and a new construction for self-complementary metacirculants of p-groups.A complementing isomorphism of a self-complementary graph is an isomorphism between the graph and its complement.For the self-complementary vertex-transitive graphs whose automorphism groups are of affine type, we have obtained a characterisation of all their complementing isomorphisms.Furthermore, we provide a construction of self-complementary metacirculants which are Cayley graphs and have insoluble automorphism groups.This is the first known example with this property in the literature.