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

zbMATH Open1295.05011arXiv1308.5490MaRDI QIDQ396944FDOQ396944

Authors: Bai Fan Chen, E. Ghorbani, K. B. Wong 

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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 O(n^k) for fixed k.

Full work available at URL: https://arxiv.org/abs/1308.5490

Recommendations

• On the eigenvalues of certain Cayley graphs and arrangement graphs
• The spectra of arrangement graphs
• Algebraic properties of arrangement graphs
• On the arrangement graph.
• Eigenvalues of the derangement graph

zbMATH Keywords

\(k\)-permutationarrangement graphcyclic decompositioneigenvalue of graph

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cited In (11)

• Alternating sign property of the perfect matching derangement graph
• The spectra of arrangement graphs
• Title not available (Why is that?)
• The spectrum of eigenvalues for certain subgraphs of the \(k\)-point fixing graph
• Largest independent sets of certain regular subgraphs of the derangement graph
• On \(k\)-complementing permutations of cyclically \(k\)-complementary graphs
• On the partition associated to the smallest eigenvalues of the \(k\)-point fixing graph
• Eigenvalues of the matching derangement graph
• The smallest eigenvalues of the 1-point fixing graph
• Cayley graph on symmetric group generated by elements fixing \(k\) points
• On the eigenvalues of certain Cayley graphs and arrangement graphs

Uses Software

• OEIS

This page was built for publication: Cyclic decomposition of \(k\)-permutations and eigenvalues of the arrangement graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396944)