Cayley graphs on abelian groups
A Cayley digraph \(\text{Cay}(G,S)\), where \(G\) is a group and \(S\) a subset of \(G\), is a DRR if \(G\) is the full automorphism group when \(G\) acts regularly as a group of automorphisms of \(\text{Cay}(G,S)\). When \(G\) is abelian and \(\text{Cay}(G,S)\) is a graph, i.e., \(S\) inverse-closed, it is said to have an automorphism group as small as possible if its automorphism group is \(G\rtimes\langle\iota\rangle\). Here, \(\iota:G\to G\) is the automorphism given by \(\iota(a)=a^{-1}\). In this article, the authors prove the following two theorems: Theorem 1. Let \(A\) be an abelian group of order \(n\). Then the number of subsets \(S\) such that \(\text{Cay}(A,S)\) is not a DRR is at most \(2^{3n/4+2(\log_{2}(n))^{2}+1}\). Theorem 2. Let \(A\) be an abelian group of order \(n\) and let \(m\) be the number of elements of order at most \(2\) of \(A\). Then the number of inverse-closed subsets \(S\) with \(\text{Aut}(\text{Cay}(A,S))>A\rtimes\langle\iota\rangle\) is at most \(2^{m/2+11n/24+2(\log_{2}(n))^{2}+2}\). Thus, the conjecture of \textit{L. Babai} and \textit{C. D. Godsil} [Eur. J. Comb. 3, 9--15 (1982; Zbl 0483.05033)] that almost all Cayley digraphs are DRRs is verified for abelian groups, and their conjecture that almost all Cayley graphs of \(A\) have an automorphism group as small as possible is also shown.
scientific article