Arrangement graph

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

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

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

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

Setting ${\displaystyle k=1}$ yields the complete graph ${\displaystyle K_{n}}$, setting ${\displaystyle k=n-1}$ yields the star graph, and setting ${\displaystyle k=n-2}$ yields the alternating group graph.^[2][4] The arrangement graph ${\displaystyle A_{n,2}}$ is the line graph of the ${\displaystyle n}$-crown graph.

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.^[2] They preserve many attractive properties of star graphs, including vertex and edge transitivity, while allowing tuning of both parameters ${\displaystyle n}$ and ${\displaystyle k}$ for suitable network size.^[1]