Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets

摘要

Let The a set of transpositions of the symmetric group S, The transposition graph Tra(T) of T is the graph with vertex set {1, 2, ..., n} and edge set {ij vertical bar (i j) is an element of T}. In this paper it is shown that if n >= 3, then the automorphism group of the transposition graph Tra(T) is isomorphic to Aut(S-n, T) = {alpha is an element of Aut(S-n) vertical bar T-alpha = T} and if T is a minimal generating set of S-n then the automorphism group of the Cayley graph Cay(S-n, T) is the semiproduct R(S-n) x Aut(S-n, T), where R(S-n) is the right regular representation of S-n. As a result, we generalize a theorem of Godsil and Royle [C.D. Godsil, G. Royle, Algebraic Graph Theory, Springer, New York, 2001, p. 53] regarding the automorphism groups of Cayley graphs on S-n: if T is a minimal generating set of S-n and the automorphism group of the transposition graph Tra(T) is trivial then the automorphism group of the Cayley graph Cay(S-n, T) is isomorphic to S-n. (c) 2005 Elsevier Inc. All rights reserved.