On the automorphism groups of almost all circulant graphs and digraphs

DOI10.26493/1855-3974.315.868zbMATH Open1323.05063arXiv1203.0707OpenAlexW2098684733WikidataQ129355152 ScholiaQ129355152MaRDI QIDQ2940101FDOQ2940101

Authors: Soumya Bhoumik, Ted Dobson, Joy Morris 

Publication date: 26 January 2015

Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)

Abstract: We show that almost all circulant graphs have automorphism groups as small as possible. Of the circulant graphs that do not have automorphism group as small as possible, we give some families of integers such that it is not true that almost all circulant graphs whose order lies in any one of these families, are normal. That almost all Cayley (di)graphs whose automorphism group is not as small as possible are normal was conjectured by the second author, so these results provide counterexamples to this conjecture. It is then shown that there is a large family of integers for which almost every circulant digraph whose order lies in this family and that does not have automorphism group as small as possible, is normal. We additionally explore the asymptotic behavior of the automorphism groups of circulant (di)graphs that are not normal, and show that no general conclusion can be obtained.

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

Recommendations

• On automorphism groups of circulant digraphs of square-free order
• Automorphism groups of circulant graphs -- a survey
• Automorphism groups of circulant digraphs with applications to semigroup theory
• scientific article; zbMATH DE number 1153465
• Asymptotic enumeration of Cayley digraphs

zbMATH Keywords

DRRautomorphism groupCayley graphcirculant graphGRR

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Cited In (23)

• Generalized Andrásfai graphs
• Automorphisms of circulants that respect partitions
• On automorphisms of circulant digraphs on \(p^{m}\) vertices, \(p\) an odd prime
• Canonization of a random circulant graph by counting walks
• Graphical Frobenius representations
• Automorphism groups of circulant digraphs with applications to semigroup theory
• Automorphism groups of rational circulant graphs
• Asymptotic enumeration of graphical regular representations
• On automorphism groups of circulant digraphs of square-free order
• Normal Cayley digraphs of generalized quaternion groups with CI-property
• On the automorphism groups of vertex-transitive Cayley digraphs of monoids
• Odd extensions of transitive groups via symmetric graphs -- the cubic case
• Generalized X-join of graphs and their automorphisms
• On automorphism groups of deleted wreath products
• Automorphism groups of circulant graphs -- a survey
• Normal Cayley digraphs of cyclic groups with CI-property
• Elusive groups of automorphisms of digraphs of small valency
• Automorphisms of Cayley graphs on generalised dicyclic groups
• On the asymptotic enumeration of Cayley graphs
• Normal Cayley digraphs of dihedral groups with CI-property
• The endomorphism monoids and automorphism groups of Cayley graphs of semigroups
• Cayley graphs on abelian groups
• The graphical regular representations of finite metacyclic \(p\)-groups

This page was built for publication: On the automorphism groups of almost all circulant graphs and digraphs

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