Abstract:  Let X be a graph of even order and I a perfect matching of the complement X’ of X. Then X is called I-almost self-complementary (I-ASC) if it is isomorphic to its I-almost complement X’-I. ASC graphs were introduced by Brian Alspach as an analogue to self-complementary graphs for (regular) graphs of even order, and ASC circulant graphs were first studied by Ted Dobson and myself (2004). In this talk I will present some results on vertex-transitive ASC graphs. This is joint work with Primož Potocnik.

While every automorphism of a graph is also an automorphism of its complement, an automorphism of an ASC graph need not preserve the “missing” perfect matching. An automorphism of an ASC graph, as well as an isomorphism from an ASC graph to its I-almost complement (called an I-antimorphism), is called fair if it preserves the associated perfect matching I. An ASC graph is called homogeneously almost self-complementary (HASC) if it admits a vertex-transitive group of fair automorphisms and a fair I-antimorphism. An HASC graph is called doubly transitive almost self complementary if the group generated by all fair automorphisms and fair I-antimorphisms acts 2-transitively on the edge set of the associated perfect matching I. A two-graph on a set O is a collection T of triples of elements of O with the property that every quadruple of elements of O contains an even number of triples in T.

In the first part of the talk we consider the problem of determination of all possible orders of HASC graphs. The complete solution of this problem would be analogous to a beautiful result by Muzychuk stating that there exists a vertex transitive self-complementary graph of order n if and only if the highest power of any prime dividing n is congruent to 1 modulo 4. We solve the problem for HASC graphs of orders twice a prime power and four times a prime. The latter of these results needed the Classification of Finite Simple Groups – which Muzychuk’s result did not - showing that the problem is significantly more difficult for ASC graphs than it is for self-complementary graphs.

In the second part of the talk we introduce brick assignments (a generalization of voltage assignments), use them to construct several particularly interesting families of HASC graphs, and present a complete classification of doubly transitive HASC graphs.

In the last part of the talk we describe a one-to-one correspondence between the isomorphism classes of self-complementary two-graphs and ASC graphs that are double covers over complete graphs. From this correspondence and Tayor's classification of 2-transitive two-graphs it follows that, for every admissible order, there exists (up to isomorphism) a unique HASC graph with the property that the group of all fair automorphisms acts 2-transitively on the edges of the associated perfect matching.