Asymptotic enumeration of graphical regular representations

2022/12/04 by Binzhou Xia, Xia, Binzhou, Zheng Shasha +1
Mathematics · #05C25 #05C30 #05E18 #20B25 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Group Theory (math.GR) #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2212.01875

openalex publication_date 2022/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We estimate the number of graphical regular representations (GRRs) of a given group with large enough order. As a consequence, we show that almost all finite Cayley graphs have full automorphism groups 'as small as possible'. This confirms a conjecture of Babai-Godsil-Imrich-Lovasz on the proportion of GRRs, as well as a conjecture of Xu on the proportion of normal Cayley graphs, among Cayley graphs of a given finite group.

Related

• On the asymptotic enumeration of Cayley graphs
• Asymptotic enumeration of Cayley digraphs
• Asymptotic enumeration of Haar graphical representations
• Graphical regular representations of (2,p)-generated groups
• On the existence and the enumeration of bipartite regular representations of Cayley graphs over abelian groups