thumb|upright=1.35|The '''arrangement graph''' <math>A_{5,2}</math>. 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.
{{distinguish|text=graphs arising from geometric line or pseudoline arrangements}}
In graph theory, the '''arrangement graph''' <math>A_{n,k}</math> is a graph defined on the vertex set consisting of all permutations of <math>k</math> distinct elements chosen from <math>\{1, 2, \ldots, n\}</math>, where two vertices are connected by an edge whenever their corresponding permutations differ in exactly one of their <math>k</math> positions.<ref name="DayTripathi1992">{{cite journal |last1=Day |first1=Khaled |last2=Tripathi |first2=Anand |title=Arrangement graphs: A class of generalized star graphs |journal=Information Processing Letters |volume=42 |issue=5 |year=1992 |pages=235–241 |doi=10.1016/0020-0190(92)90030-Y |issn=0020-0190}}</ref><ref name="Lin2003">{{cite journal |last=Lin |first=Chin-Tsai |title=Embedding k(n−k) edge-disjoint spanning trees in arrangement graphs |journal=Journal of Parallel and Distributed Computing |volume=63 |issue=12 |year=2003 |pages=1277–1287 |doi=10.1016/S0743-7315(03)00107-2 |issn=0743-7315}}</ref>
== Properties == The <math>(n,k)</math>-arrangement graph has <math>n!/(n-k)!</math> vertices, is regular with vertex degree <math>k(n-k)</math>, and is <math>k(n-k)</math>-connected. It has graph diameter <math>\lfloor 3k/2 \rfloor</math> and average distance <math>H_k + k(k-2)/n</math>, where <math>H_k = \sum_{i=1}^{k} \frac{1}{i}</math> is the <math>k</math>th harmonic number. The arrangement graph is both vertex-transitive and edge-transitive.<ref name="DayTripathi1992" /><ref name="Lin2003" />
The <math>(n,k)</math>-arrangement graph can be decomposed into <math>n</math> subgraphs isomorphic to <math>A_{n-1,k-1}</math> by fixing each different element in one particular position.<ref name="Lin2003" />
The eigenvalues of the adjacency matrix of an arrangement graph are integers. For fixed <math>k</math> and sufficiently large <math>n</math>, <math>-k</math> is the only negative eigenvalue in the spectrum.<ref name="AraujoBratten2017">{{cite journal |last1=Araujo |first1=José O. |last2=Bratten |first2=Tim |title=The spectra of arrangement graphs |journal=Linear Algebra and Its Applications |volume=530 |year=2017 |pages=461–469 |doi=10.1016/j.laa.2017.05.032 |issn=0024-3795|arxiv=1612.04747 }}</ref>
== Special cases == Setting <math>k = 1</math> yields the complete graph <math>K_n</math>, setting <math>k = n-1</math> yields the star graph, and setting <math>k = n-2</math> yields the alternating group graph.<ref name="Lin2003" /><ref name="WangFeng2014">{{cite journal |last1=Wang |first1=Shiying |last2=Feng |first2=Kai |title=Fault tolerance in the arrangement graphs |journal=Theoretical Computer Science |volume=533 |year=2014 |pages=64–71 |doi=10.1016/j.tcs.2014.03.025 |issn=0304-3975}}</ref> The arrangement graph <math>A_{n,2}</math> is the line graph of the <math>n</math>-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.<ref name="Lin2003" /> They preserve many attractive properties of star graphs, including vertex and edge transitivity, while allowing tuning of both parameters <math>n</math> and <math>k</math> for suitable network size.<ref name="DayTripathi1992" />
== References == {{reflist}}
{{graph-stub}}
Category:Parametric families of graphs Category:Regular graphs