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-
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 [👁 {
,
👁 {
n,
k👁 }
👁 }
].
Special cases of 👁 A_(n,k)
are summarized in the following table and illustrated above.
See also
Alternating Group Graph, Permutation Star GraphExplore with Wolfram|Alpha
More things to try:
References
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 GraphCite this as:
Weisstein, Eric W. "Arrangement Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ArrangementGraph.html