Premium
The symmetry property of ( n , k ) ‐arrangement graph
Author(s) -
Yin FuGang,
Feng YanQuan,
Zhou JinXin,
Guo YuHong
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22690
Subject(s) - combinatorics , mathematics , vertex transitive graph , edge transitive graph , voltage graph , cayley graph , discrete mathematics , graph automorphism , symmetric graph , circulant graph , complement graph , petersen graph , distance regular graph , cubic graph , line graph , 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 ) .