On the equivalence between a conjecture of Babai-Godsil and a conjecture of Xu concerning the enumeration of Cayley graphs

Keywords: regular representation, Cayley graph, automorphism group, asymptotic enumeration, graphical regular representation, GRR, normal Cayley graph, Babai-Godsil conjecture, Xu conjecture

Abstract

In this paper we show that two distinct conjectures, the first proposed by Babai and Godsil in 1982 and the second proposed by Xu in 1998, concerning the asymptotic enumeration of Cayley graphs are in fact equivalent. This result follows from a more general theorem concerning the asymptotic enumeration of a certain family of Cayley graphs.

Published
2021-04-01
Section
Articles