Cyclic decomposition of k-permutations and eigenvalues of the arrangement graphs

摘要: The (n,k)-arrangement graph A(n,k) is a with all the k-permutations of an n-element set as vertices where two are adjacent if they agree in exactly k-1 positions. We introduce cyclic decomposition for and show that this gives rise to very fine equitable partition A(n,k). This can be employed compute complete eigenvalues (of adjacency matrix) Consequently, we determine small values k. Finally, any eigenvalue Johnson J(n,k) -k smallest multiplicity O(n^k) fixed