On the eigenvalues of certain Cayley graphs and arrangement graphs

DOI10.1016/J.LAA.2013.11.035zbMATH Open1285.05087arXiv1310.8078OpenAlexW2963768904MaRDI QIDQ2442263FDOQ2442263

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)

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)