Babai–Godsil conjecture on almost all Cayley graphs being GRRs
Let be a finite group, and let be an inverse-closed subset of . The Cayley graph has vertex set and edges determined by ; a graphical regular representation (GRR) is a Cayley graph whose full automorphism group is acting regularly on its vertices. A group is generalised dicyclic if it belongs to the corresponding excluded family, and an abelian group has exponent greater than when some element has order greater than .
Babai–Godsil conjecture. If is not generalised dicyclic or abelian of exponent greater than , then for almost all inverse-closed subsets of , is a GRR.
This conjecture concerns the asymptotic prevalence of graphical regular representations among Cayley graphs.
References
3 papers in this index state this conjecture (2013–2020). The statement above is taken from the most recent of them; the others are arXiv:1911.09444, arXiv:1306.3747.
Status
- Solved: Binzhou Xia and Shasha Zheng. Asymptotic enumeration of graphical regular representations (arXiv, 2022) https://arxiv.org/abs/2212.01875
Source: Joy Morris, Mariapia Moscatiello and Pablo Spiga, “On the asymptotic enumeration of Cayley graphs”, arXiv:2005.07687 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.