Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups

View/ Open
Issue date
2020Suggested citation
Dalfó, Cristina;
Fiol, Miguel Angel;
.
(2020)
.
Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups.
Linear Algebra and its Applications, 2020, vol. 597, p. 94-112.
https://doi.org/10.1016/j.laa.2020.03.015.
Metadata
Show full item recordAbstract
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.
Is part of
Linear Algebra and its Applications, 2020, vol. 597, p. 94-112European research projects
The following license files are associated with this item:
Related items
Showing items related by title, author, creator and subject.
-
The spectra of lifted digraphs
Dalfó, Cristina; Fiol, Miguel Angel; Sirán, Jozef (Springer, 2019-01-02)We present a method to derive the complete spectrum of the lift Γα of a base digraph Γ , with voltage assignment α on a (finite) group G. The method is based on assigning to Γ a quotient-like matrix whose entries are ... -
A general method to obtain the spectrum and local spectra of a graph from its regular partitions
Dalfó, Cristina; Fiol, Miguel Angel (International Linear Algebra Society, 2020-07-12)It is well known that, in general, part of the spectrum of a graph can be obtained from the adjacency matrix of its quotient graph given by a regular partition. In this paper, a method that gives all the spectrum, and also ... -
The spectral excess theorem for graphs with few eigenvalues whose distance- 2 or distance-1-or-2 graph is strongly regular
Dalfó, Cristina; Fiol, Miguel Angel; Koolen, Jack (Taylor & Francis, 2018-07-13)We study regular graphs whose distance-2 graph or distance-1-or-2 graph is strongly regular. We provide a characterization of such graphs Γ (among regular graphs with few distinct eigenvalues) in terms of the spectrum and ...