The arrangement graph A 5 , 2 {\displaystyle A_{5,2}}. For the numbers 1 through 5, each vertex is a permutation of 2 numbers. Two vertices are connected if changing exactly one digit of a vertex changes it into the other.

In graph theory, the arrangement graph A n , k {\displaystyle A_{n,k}} is a graph defined on the vertex set consisting of all permutations of k {\displaystyle k} distinct elements chosen from { 1 , 2 , … , n } {\displaystyle \{1,2,\ldots ,n\}}, where two vertices are connected by an edge whenever their corresponding permutations differ in exactly one of their k {\displaystyle k} positions.

Properties

The ( n , k ) {\displaystyle (n,k)}-arrangement graph has n ! / ( n − k ) ! {\displaystyle n!/(n-k)!} vertices, is regular with vertex degree k ( n − k ) {\displaystyle k(n-k)}, and is k ( n − k ) {\displaystyle k(n-k)}-connected. It has graph diameter ⌊ 3 k / 2 ⌋ {\displaystyle \lfloor 3k/2\rfloor } and average distance H k + k ( k − 2 ) / n {\displaystyle H_{k}+k(k-2)/n}, where H k = ∑ i = 1 k 1 i {\displaystyle H_{k}=\sum _{i=1}^{k}{\frac {1}{i}}} is the k {\displaystyle k}th harmonic number. The arrangement graph is both vertex-transitive and edge-transitive.

The ( n , k ) {\displaystyle (n,k)}-arrangement graph can be decomposed into n {\displaystyle n} subgraphs isomorphic to A n − 1 , k − 1 {\displaystyle A_{n-1,k-1}} by fixing each different element in one particular position.

The eigenvalues of the adjacency matrix of an arrangement graph are integers. For fixed k {\displaystyle k} and sufficiently large n {\displaystyle n}, − k {\displaystyle -k} is the only negative eigenvalue in the spectrum.

Special cases

Setting k = 1 {\displaystyle k=1} yields the complete graph K n {\displaystyle K_{n}}, setting k = n − 1 {\displaystyle k=n-1} yields the star graph, and setting k = n − 2 {\displaystyle k=n-2} yields the alternating group graph. The arrangement graph A n , 2 {\displaystyle A_{n,2}} is the line graph of the n {\displaystyle n}-crown graph.

Applications

Arrangement graphs were proposed as a generalization of star graphs to provide a more flexible choice of network parameters when designing an interconnection network for multiprocessor or multicomputer systems. They preserve many attractive properties of star graphs, including vertex and edge transitivity, while allowing tuning of both parameters n {\displaystyle n} and k {\displaystyle k} for suitable network size.