Self-complementary two-graphs and almost self-complementary double covers

摘要

A graph X is called almost self-complementary with respect to a perfect matching if it is isomorphic to the graph obtained from its complement by removing the edges of . A two-graph on a vertex set Ω is a collection of 3-subsets of Ω such that each 4-subset of Ω contains an even number of elements of . In this paper we investigate the relationship between self-complementary two-graphs and double covers over complete graphs that are almost self-complementary with respect to a set of fibres. In particular, we classify all doubly transitive self-complementary two-graphs, and thus all almost self-complementary graphs with an automorphism group acting 2-transitively on the corresponding perfect matching.