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

MaRDI QIDQ396944zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1308.5490, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p22

zbMATH Keywords

\(k\)-permutationarrangement graphcyclic decompositioneigenvalue of graph

Mathematics Subject Classification ID

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

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.

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

Cited in

(12)

• Cayley graph on symmetric group generated by elements fixing \(k\) points
• On the partition associated to the smallest eigenvalues of the \(k\)-point fixing graph
• The symmetry property of (n,k)‐arrangement graph
• The smallest eigenvalues of the 1-point fixing graph
• Largest independent sets of certain regular subgraphs of the derangement graph
• Some results of the minimum edge dominating energy of the Cayley graphs for the finite group \(S_n\)
• On the eigenvalues of certain Cayley graphs and arrangement graphs
• Alternating sign property of the perfect matching derangement graph
• On \(k\)-complementing permutations of cyclically \(k\)-complementary graphs
• The spectrum of eigenvalues for certain subgraphs of the \(k\)-point fixing graph
• Eigenvalues of the matching derangement graph
• The spectra of arrangement graphs

Describes a project that uses

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)