Arrangement Graph


The (n,k)-arrangement graph A_(n,k) is defined as the graph on the vertex set consisting of the permutations of {1,2,...,n} containing at most k elements where vertices are connected by edges whenever two permutations differ in exactly one of their k positions. The (n,k)-arrangement graph has n!/(n-k)! nodes, is regular of vertex degree k(n-k), k(n-k)-connected, has graph diameter |_3k/2_|, and is vertex-Vertex-Transitive Graph and edge-transitive (Day and Tripathi 1992).

The arrangement graph A_(n,2) is the line graph of the n-crown graph.

Precomputed properties of arrangement graphs are available in the Wolfram Language as GraphData[{"ArrangementGraph", {n, k}}].

Special cases of A_(n,k) are summarized in the following table and illustrated above.

See also

Alternating Group Graph, Permutation Star Graph

Explore with Wolfram|Alpha


Day, K. and Tripathi, A. "Arrangement Graphs: A Class of Generalized Star Graphs." Inform. Proc. Lett. 42, 235-241, 1992.

Referenced on Wolfram|Alpha

Arrangement Graph

Cite this as:

Weisstein, Eric W. "Arrangement Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications