The symmetry property of ( n , k ) ‐arrangement graph

The ( n , k ) ‐ arrangement graph   A ( n , k ) with 1 ≤ k ≤ n − 1 , is the graph with vertex set the ordered k ‐tuples of distinct elements in { 1 , 2 , … , n } and with two k ‐tuples adjacent if they differ in exactly one of their coordinates. The ( n , k ) ‐arrangement graph was proposed by Day and Tripathi in 1992, and is a widely studied interconnection network topology. The Johnson graph   J ( n , k ) with 1 ≤ k ≤ n − 1 , is the graph with vertex set the k ‐element subsets of { 1 , 2 , … , n } , and with two k ‐element subsets adjacent if their intersection has k − 1 elements. In 1989, Brouwer, Cohen and Neumaier determined the automorphism group of J ( n , k ) , and in 2015, Dobson and Malnič proved that J ( n , k ) a is Cayley graph if and only if ( n , k ) = ( 8 , 3 ) , ( 32 , 3 ) or ( n , 2 ) with n ≡ 3 ( mod 4 ) being a prime‐power. In this article we prove that Aut ( A ( n , k ) ) ≅ S n × S k , and as a byproduct, A ( n , k ) is a normal cover of J ( n , k ) . Furthermore, A ( n , k ) is a Cayley graph if and only if ( n , k ) = ( 33 , 4 ) , ( 11 , 4 ) , ( 9 , 4 ) , ( 12 , 5 ) , ( 8 , 5 ) , ( 9 , 6 ) , ( 32 , 29 ) , ( 33 , 30 ) , ( n , 1 ) , ( n , n − 1 ) , ( n , n − 2 ) , ( q , 2 ) or ( q + 1 , 3 ) , where q is a prime‐power. Note that the graph A ( n , n − 1 ) is called the n ‐ star graph , and its automorphism group can be deduced from a general result given by Feng in 2006. In 1998, Chiang and Chen proved that A ( n , n − 2 ) is a Cayley graph on the alternating group A n , and in 2011, Zhou determined the automorphism group of A ( n , n − 2 ) .