Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups
Loading...
Date
2020
Authors
Dalfó, Cristina
Fiol, Miguel Angel
Other authors
Impact
Export
Share
Journal Title
Journal ISSN
Volume Title
Abstract
In this paper, we present a method to obtain regular (or equitable) partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups on n letters. We prove that every partition of the number n gives rise to a regular partition of the Cayley graph. By using representation theory, we also obtain the complete spectra and the eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide a method to find all the eigenvalues and eigenvectors of such (di)graphs, based on their irreducible representations. As examples, we apply this method to the pancake graphs P(n) and to a recent known family of mixed graphs Γ(d, n, r) (having edges with and without direction). As a byproduct, the existence of perfect codes s in P(n) allows us to give a lower bound for the multiplicity of its eigenvalue −1.
Citation
Journal or Serie
Linear Algebra and its Applications, 2020, vol. 597, p. 94-112