Most rigid representations and Cayley index

DOI10.26493/2590-9770.1242.809MaRDI QIDQ5198010zbMATH OpenOpenAlexWikidataFDO

Authors Joy Morris, Josh Tymburski

Publication date 2 October 2019

Published in The Art of Discrete and Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

automorphismsCayley graphCayley indexGRRMRR

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Extremal problems in graph theory (05C35)

Abstract: For any finite group $G$, a natural question to ask is the order of the smallest possible automorphism group for a Cayley graph on $G$. A particular Cayley graph whose automorphism group has this order is referred to as an MRR (Most Rigid Representation), and its Cayley index is a numerical indicator of this value. Study of GRRs showed that with the exception of two infinite families and seven individual groups, every group admits a Cayley graph whose MRR is a GRR, so that the Cayley index is 1. The full answer to the question of finding the smallest possible Cayley index for a Cayley graph on a fixed group was almost completed in previous work, but the precise answers for some finite groups and one infinite family of groups were left open. We fill in the remaining gaps to completely answer this question.

Recommendations

• On the asymptotic enumeration of Cayley graphs
• Asymptotic enumeration of Cayley digraphs
• Digraphs with small automorphism groups that are Cayley on two nonisomorphic groups
• On finite dual Cayley graphs
• Isomorphisms of connected Cayley digraphs

Cites work

• Graphen mit transitiver Automorphismengruppe
• Graphical regular representations of alternating, symmetric and miscellaneous small groups
• Graphical Regular Representations of Non-Abelian Groups, I
• Graphical Regular Representations of Non-Abelian Groups, II
• Groups of graphs of groups
• scientific article; zbMATH DE number 3137403 (Why is no real title available?)
• scientific article; zbMATH DE number 3747160 (Why is no real title available?)
• scientific article; zbMATH DE number 3501517 (Why is no real title available?)
• scientific article; zbMATH DE number 3394177 (Why is no real title available?)
• On a Theorem of Sabidussi
• On automorphisms of Cayley graphs
• On graphs with regular groups
• On the action of non-Abelian groups on graphs
• Vertex-transitive graphs

Cited in

(6)

• Graphical Frobenius representations
• Most rigid representation and Cayley index of finitely generated groups
• On the flag graphs of regular abstract polytopes: Hamiltonicity and Cayley index
• A classification of the graphical \(m\)-semiregular representation of finite groups
• scientific article; zbMATH DE number 7678748 (Why is no real title available?)
• On the existence and the enumeration of bipartite regular representations of Cayley graphs over abelian groups

Describes a project that uses

Uses Software

• GAP
• SageMath

This page was built for publication: Most rigid representations and Cayley index

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