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

DOI10.1016/J.LAA.2020.03.015zbMATH Open1437.05134arXiv1906.05851OpenAlexW3010887733MaRDI QIDQ2174095FDOQ2174095

Authors: C. Dalfó, Miquel Angel Fiol 

Publication date: 17 April 2020

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

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 $Gamma(d,n,r)$ (having edges with and without direction). As a byproduct, the existence of perfect codes in $P(n)$ allows us to give a lower bound for the multiplicity of its eigenvalue $-1$.

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

Recommendations

• A general method to obtain the spectrum and local spectra of a graph from its regular partitions
• The spectrum of Cayley graphs on symmetric group generated by certain subset of \(r\)-cycles
• On the partitions associated with the smallest eigenvalues of certain Cayley graphs on symmetric group generated by cycles
• On the characteristic polynomial of \(n\)-Cayley digraphs
• On the spectrum of Cayley graphs

zbMATH Keywords

spectrumrepresentation theorysymmetric groupregular partitionpancake graphlifted digraphlifted graphnew mixed graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Eigenvalues, singular values, and eigenvectors (15A18) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Representations of finite symmetric groups (20C30)

Cites Work

• Title not available (Why is that?)
• Problems in algebraic combinatorics
• A group-theoretic model for symmetric interconnection networks
• Generating all graph coverings by permutation voltage assignments
• Bounds for sorting by prefix reversal
• Vertex-symmetric digraphs with small diameter
• On the Diameter of the Pancake Network
• On average and highest number of flips in pancake sorting
• Representations and characters of groups.
• Cycle prefix digraphs for symmetric interconnection networks
• A new general family of mixed graphs
• The spectra of lifted digraphs
• An algebraic approach to lifts of digraphs
• On Some Structural Properties of Star and Pancake Graphs
• Spectra and eigenspaces of arbitrary lifts of graphs

Cited In (4)

• Eigenvalues of Cayley graphs
• Binomial Cayley graphs and applications to dynamics on finite spaces
• Some integer values in the spectra of burnt pancake graphs
• Lower bounds for the spectral norm of digraphs

Uses Software

• OEIS

This page was built for publication: Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups

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