Arrangement graph

In graph theory, the arrangement graph is a graph defined on the vertex set consisting of all permutations of distinct elements chosen from, where two vertices are connected by an edge whenever their corresponding permutations differ in exactly one of their positions.

Properties

The -arrangement graph has vertices, is regular with vertex degree, and is -connected. It has graph diameter and average distance, where is the th harmonic number. The arrangement graph is both vertex-transitive and edge-transitive.
The -arrangement graph can be decomposed into subgraphs isomorphic to by fixing each different element in one particular position.
The eigenvalues of the adjacency matrix of an arrangement graph are integers. For fixed and sufficiently large, is the only negative eigenvalue in the spectrum.

Special cases

Setting yields the complete graph, setting yields the star graph, and setting yields the alternating group graph. The arrangement graph is the line graph of the -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 and for suitable network size.