Automorphism Groups of Cayley Graphs Generated by General Transposition Sets

Journal article (2024)

Authors

DC Gijswijt Discrete Mathematics and Optimization - EEMCS
F.J.J. Meijer Discrete Mathematics and Optimization - EEMCS
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
More Info
expand_more

Published Date

2024

Language

English

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

Abstract

In this paper we study the Cayley graph Cay(Sn, T) of the symmetric group Sn generated by a set of transpositions T. We show that for n ≥ 5 the Cayley graph is normal. As a corollary, we show that its automorphism group is a direct product of Sn and the automorphism group of the transposition graph associated to T. This provides an affirmative answer to a conjecture raised by A. Ganesan, Cayley graphs and symmetric interconnection networks, showing that Cay(Sn, T) is normal if and only if the transposition graph is not C4 or Kn.