On the eigenvalues of certain Cayley graphs and arrangement graphs

DOI10.1016/J.LAA.2013.11.035MaRDI QIDQ2442263zbMATH OpenOpenAlexFDO

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

Publication date 2 April 2014

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

Cayley graphsymmetric grouparrangement graphspectrum integrality

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Integral representations of finite groups (20C10)

Abstract: In this paper, we show that the eigenvalues of certain classes of Cayley graphs are integers. The (n,k,r)-arrangement graph A(n,k,r) is a graph with all the k-permutations of an n-element set as vertices where two k-permutations are adjacent if they differ in exactly r positions. We establish a relation between the eigenvalues of the arrangement graphs and the eigenvalues of certain Cayley graphs. As a result, the conjecture on integrality of eigenvalues of A(n,k,1) follows.

Recommendations

• Cyclic decomposition of k-permutations and eigenvalues of the arrangement graphs
• The spectra of arrangement graphs
• Algebraic properties of arrangement graphs
• Integral Cayley graphs and groups
• Eigenvalues of the derangement graph

Cites work

• scientific article; zbMATH DE number 3526920 (Why is no real title available?)
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• scientific article; zbMATH DE number 2042680 (Why is no real title available?)
• Arrangement graphs: A class of generalized star graphs
• Conditional fault tolerance of arrangement graphs
• Conditional matching preclusion for the arrangement graphs
• Cyclic decomposition of k-permutations and eigenvalues of the arrangement graphs
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Feasibility conditions for the existence of walk-regular graphs
• Generating a random permutation with random transpositions
• Linearly many faults in arrangement graphs
• Matrix Analysis
• On Cayley graphs on the symmetric group generated by transpositions
• On the arrangement graph.
• Spectra of Cayley graphs
• Spectra of graphs
• Spectrum of Cayley graphs on the symmetric group generated by transpositions
• The distance spectra of Cayley graphs of Coxeter groups
• The number of shortest paths in the arrangement graph
• The paths embedding of the arrangement graphs with prescribed vertices in given position
• Which Cayley graphs are integral?

Cited in

(18)

• On the partitions associated with the smallest eigenvalues of certain Cayley graphs on symmetric group generated by cycles
• Cyclic decomposition of k-permutations and eigenvalues of the arrangement graphs
• Alternating sign property of the perfect matching derangement graph
• Ramanujan Cayley graphs of some sporadic and linear groups
• The spectra of arrangement graphs
• Eigenvalues of Cayley graphs
• The spectrum of eigenvalues for certain subgraphs of the k-point fixing graph
• scientific article; zbMATH DE number 7349613 (Why is no real title available?)
• Largest independent sets of certain regular subgraphs of the derangement graph
• On the partition associated to the smallest eigenvalues of the k-point fixing graph
• Eigenvalues of the matching derangement graph
• The symmetry property of (n,k)‐arrangement graph
• The smallest eigenvalues of the 1-point fixing graph
• The spectrum of Cayley graphs on symmetric group generated by certain subset of \(r\)-cycles
• Cayley graph on symmetric group generated by elements fixing k points
• Upper bounds for Steklov eigenvalues of subgraphs of polynomial growth Cayley graphs
• Algebraic properties of arrangement graphs
• On the algebraic combinatorics of injections

This page was built for publication: On the eigenvalues of certain Cayley graphs and arrangement graphs

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