On the asymptotic enumeration of Cayley graphs
Loading...
Date
2021
Authors
Morris, Joy
Moscatiello, Mariapia
Spiga, Pablo
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Abstract
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.
Description
Open access article. Creative Commons Attribution 4.0 International license (CC BY 4.0) applies
Keywords
Regular representation , Cayley graph , Automorphism group , Asymptotic enumeration , Graphical regular representation , GRR , Normal Cayley graph , Babai-Godsil conjecture , Xu conjecture
Citation
Morris, J., Moscatiello, M., & Spiga, P. (2021). On the asymptotic enumeration of Cayley graphs. Annali di Matematica pura e Applicata, 201(3), 1417-1461. https://doi.org/10.1007/s10231-021-01163-w