Most rigid representations and Cayley index

  • Joy Morris University of Lethbridge, Canada
  • Josh Tymburski University of Lethbridge, Canada
Keywords: Cayley graph, Cayley index, GRR, MRR, automorphisms


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 thirteen 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.