Automorphism Groups of Cayley Graphs Generated by General Transposition Sets

Journal Article (2024)
Author(s)

Dion Gijswijt (TU Delft - Discrete Mathematics and Optimization)

Frank Meijer (TU Delft - Discrete Mathematics and Optimization)

Research Group
Discrete Mathematics and Optimization
DOI related publication
https://doi.org/10.37236/12771
More Info
expand_more
Publication Year
2024
Language
English
Research Group
Discrete Mathematics and Optimization
Issue number
3
Volume number
31
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

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.