Math & Computer Science

Permanent URI for this community

Now showing 1 - 1 of 1

On the asymptotic enumeration of Cayley graphs
(Springer, 2021) Morris, Joy; Moscatiello, Mariapia; Spiga, Pablo
In this paper, we are interested in the asymptotic enumeration of Cayley graphs. It has previously been shown that almost every Cayley digraph has the smallest possible auto- morphism group: that is, it is a digraphical regular representation (DRR). In this paper, we approach the corresponding question for undirected Cayley graphs. The situation is com- plicated by the fact that there are two infinite families of groups that do not admit any graphical regular representation (GRR). The strategy for digraphs involved analysing sepa- rately the cases where the regular group R has a nontrivial proper normal subgroup N with the property that the automorphism group of the digraph fixes each N-coset setwise, and the cases where it does not. In this paper, we deal with undirected graphs in the case where the regular group has such a nontrivial proper normal subgroup.