Asymptotic enumeration of graphical regular representations

DOI10.1112/PLMS.12563MaRDI QIDQ6139774zbMATH OpenOpenAlexFDO

Authors Binzhou Xia, Shasha Zheng

Publication date 19 December 2023

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2212.01875

zbMATH Keywords

Cayley digraphCayley graphdigraphical regular representation

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Group actions on combinatorial structures (05E18) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Arithmetic and combinatorial problems involving abstract finite groups (20D60)

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.

Recommendations

• Asymptotic enumeration of Cayley digraphs
• On the asymptotic enumeration of Cayley graphs
• Normal Cayley digraphs of cyclic groups with CI-property
• On the automorphism groups of almost all circulant graphs and digraphs
• Cayley graphs on abelian groups
• The diameters of almost all Cayley digraphs
• Normal Cayley graphs of finite groups
• The automorphism groups of minimal infinite circulant digraphs
• scientific article; zbMATH DE number 1471065
• On normality of n-Cayley graphs

Cites work

• Asymptotic enumeration of Cayley digraphs
• Automorphism groups and isomorphisms of Cayley digraphs
• Automorphisms of Cayley graphs on generalised dicyclic groups
• Cayley graphs on abelian groups
• Enumerating boundedly generated finite groups.
• Finite digraphs with given regular automorphism groups
• Finite transitive groups having many suborbits of cardinality at most 2 and an application to the enumeration of Cayley graphs
• scientific article; zbMATH DE number 3747160 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• Normal Cayley graphs of finite groups
• On a Theorem of Sabidussi
• On primitive overgroups of quasiprimitive permutation groups
• On the action of non-Abelian groups on graphs
• On the asymptotic enumeration of Cayley graphs
• On the automorphism groups of almost all Cayley graphs
• On the equivalence between a conjecture of Babai-Godsil and a conjecture of Xu concerning the enumeration of Cayley graphs
• On the existence of Frobenius digraphical representations
• On the existence of graphical Frobenius representations and their asymptotic enumeration
• On the full automorphism group of a graph
• On the non-existence of graphs with transitive generalized dicyclic groups
• Vertex-transitive graphs

Cited in

(9)

• Asymptotic enumeration of two-dimensional posets
• Cayley graphs on abelian groups
• Asymptotic enumeration of cographs
• Asymptotic Enumeration of Graph Classes with Many Components
• CAYLEY GRAPHS AND GRAPHICAL REGULAR REPRESENTATIONS
• Using Schur rings to produce GRRs for dihedral groups
• On automorphism groups of the conjugacy class type Cayley graphs on the symmetric and alternating groups
• Haar graphical representations of finite groups and an application to poset representations
• A census of Cayley graphs

This page was built for publication: Asymptotic enumeration of graphical regular representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139774)