Paper Info
Title
The Symmetry Property Of ( N , K )-Arrangement Graph
Abstract
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 , horizontal ellipsis , 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 , horizontal ellipsis , 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 Malnic proved that J ( n , k ) a is Cayley graph if and only if ( n , k ) = ( 8 , 3 ), ( 32 , 3 ) or ( n , 2 ) with n equivalent to 3 ( mod 4 ) being a prime-power. In this article we prove that Aut ( A ( n , k ) ) approximately equal to S n x 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 ).
Year
DOI
Venue
2021
10.1002/jgt.22690
JOURNAL OF GRAPH THEORY
Keywords
DocType
Volume
cayley graph, johnson graph, (n, k)-arrangement graph
Journal
98
Issue
ISSN
Citations 
2
0364-9024
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Fugang Yin101.35
Yan-quan Feng235041.80
Jin-Xin Zhou315625.22
Yu-Hong Guo400.34