Arrangement graph

The arrangement graph $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}$ is a graph defined on the vertex set consisting of all permutations of $k$ distinct elements chosen from $\{1,2,\dots ,n\}$, where two vertices are connected by an edge whenever their corresponding permutations differ in exactly one of their $k$ positions.

Properties

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

The $(n,k)$-arrangement graph can be decomposed into $n$ subgraphs isomorphic to $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$ and sufficiently large $n$, $-k$ is the only negative eigenvalue in the spectrum.

Special cases

Setting $k=1$ yields the complete graph $K_n$, setting $k=n-1$ yields the star graph, and setting $k=n-2$ yields the alternating group graph. The arrangement graph $A_{n,2}$ is the line graph of the $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$ and $k$ for suitable network size.