Geodesic
Cyclic decomposition of \(k\)-permutations and eigenvalues of the arrangement graphs
Bai Fan Chen ; Ebrahim Ghorbani1 ; Kok Bin Wong2
1Institute for Research in Fundamental Sciences (IPM)
2University of Malaya
The electronic journal of combinatorics, Tome 20 (2013) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The $(n,k)$-arrangement graph $A(n,k)$ is a graph with all the $k$-permutations of an $n$-element set as vertices where two $k$-permutations are adjacent if they agree in exactly $k-1$ positions. We introduce a cyclic decomposition for $k$-permutations and show that this gives rise to a very fine equitable partition of $A(n,k)$. This equitable partition can be employed to compute the complete set of eigenvalues (of the adjacency matrix) of $A(n,k)$. Consequently, we determine the eigenvalues of $A(n,k)$ for small values of $k$. Finally, we show that any eigenvalue of the Johnson graph $J(n,k)$ is an eigenvalue of $A(n,k)$ and that $-k$ is the smallest eigenvalue of $A(n,k)$ with multiplicity ${\cal O}(n^k)$ for fixed $k$.
DOI : 10.37236/3711
Classification : 05A05, 05C50
Mots-clés : \(k\)-permutation, cyclic decomposition, arrangement graph, eigenvalue of graph

Bai Fan Chen    ; Ebrahim Ghorbani  1   ; Kok Bin Wong  2

1 Institute for Research in Fundamental Sciences (IPM)
2 University of Malaya 
@article{10_37236_3711,
     author = {Bai Fan Chen and Ebrahim Ghorbani and Kok Bin Wong},
     title = {Cyclic decomposition of \(k\)-permutations and eigenvalues of the arrangement graphs},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {4},
     doi = {10.37236/3711},
     zbl = {1295.05011},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3711/}
}
TY  - JOUR
AU  - Bai Fan Chen
AU  - Ebrahim Ghorbani
AU  - Kok Bin Wong
TI  - Cyclic decomposition of \(k\)-permutations and eigenvalues of the arrangement graphs
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3711/
DO  - 10.37236/3711
ID  - 10_37236_3711
ER  - 
%0 Journal Article
%A Bai Fan Chen
%A Ebrahim Ghorbani
%A Kok Bin Wong
%T Cyclic decomposition of \(k\)-permutations and eigenvalues of the arrangement graphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/3711/
%R 10.37236/3711
%F 10_37236_3711
Bai Fan Chen; Ebrahim Ghorbani; Kok Bin Wong. Cyclic decomposition of \(k\)-permutations and eigenvalues of the arrangement graphs. The electronic journal of combinatorics, Tome 20 (2013) no. 4. doi: 10.37236/3711

Cité par Sources :