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

作者：Feng YQ^*

来源：Journal of Combinatorial Theory - Series B, 2006, 96(1): 67-72.

DOI：10.1016/j.jctb.2005.06.010

• Cayley graph
• symmetric group
• automorphisin group

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.

• 出版日期2006-1
• 单位北京交通大学