Almost self-complementary circulant graphs. (Q1427468)

The concept of an {almost self-complementary graph} has been introduced by B. Alspach to get around the restriction that the order of a self-complementary regular graph must be odd. An {almost complement} of a graph \(\Gamma\) of even order is a graph obtained by removing the edges of a 1-factor from the complement of \( \Gamma \). A graph of even order is almost self-complementary if it is isomorphic to at least one of its almost complements. The focus of the paper is on almost self-complementary circulant graphs \(\Gamma\) (graphs whose full automorphism group contains a regular cyclic subgroup) with the additional property that both \(\Gamma\) and at least one of its isomorphic almost complements have the same regular cyclic subgroup of the full automorphism group of \( \Gamma\). The authors show that an almost self-complementary circulant graph of order \(2n\) with this additional property exists if and only if every prime divisor of \(n\) is congruent to \(1\) modulo \(4\). This is an analogue of a result of Fronček et al. [\textit{D. Fronček}, \textit{A. Rosa} and \textit{J. Širáň}, Eur. J. Comb. 17, No. 7, 625--628 (1996; Zbl 0869.05036)] who proved the same arithmetic condition on \(n\) to be both necessary and sufficient for the existence of a self-complementary circulant of order \(n\), and one of the proofs presented in this paper follows essentially along the same lines as the proof of Fronček et al. In addition to proving their main theorem, the authors present a considerable amount of information on the structure of cyclically almost self-complementary circulants (that often happen to be a wreath product of a circulant graph of order \(n\) with \(K_2\) or its complement). The last section of the paper contains results concerning almost self-complementary Cayley graphs on non-cyclic groups whose isomorphic almost complement is a Cayley graph of the same group. All Cayley graphs of the dihedral group \(D_n\) such that \(n\) is odd and two Cayley graphs on \(D_n\) are isomorphic if and only if there exists a group automorphism of \(D_n\) mapping one to the other.