×
Dalfó, C.; Fiol, M. A.

Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups. (English) Zbl 1437.05134

Linear Algebra Appl. 597, 94-112 (2020).
Summary: 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\).

Cited in 2 Documents

MSC:

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

Keywords:

lifted digraph; lifted graph; regular partition; spectrum; symmetric group; representation theory; pancake graph; new mixed graph

Software:

OEIS
Cite Review PDF
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Sorting by prefix reversal (or ”flipping pancakes”). You can only reverse segments that include the initial term of the current permutation; a(n) is the number of reversals that are needed to transform an arbitrary permutation of n letters to the identity permutation.

References:

[1] Akers, S. B.; Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566 (1989) · Zbl 0678.94026
[2] Burrow, M., Representation Theory of Finite Groups (1993), Dover: Dover New York
[3] Cibulka, J., On average and highest number of flips in pancake sorting, Theor. Comput. Sci., 412, 822-834 (2011) · Zbl 1211.68138
[4] Comellas, F.; Fiol, M. A., Vertex-symmetric digraphs with small diameter, Discrete Appl. Math., 58, 1, 1-12 (1995) · Zbl 0822.05033
[5] Dalfó, C., A new general family of mixed graphs, Discrete Appl. Math., 269, 99-106 (2019) · Zbl 1421.05035
[6] Dalfó, C.; Fiol, M. A.; Miller, M.; Ryan, J.; Širáň, J., An algebraic approach to lifts of digraphs, Discrete Appl. Math., 269, 68-76 (2019) · Zbl 1421.05048
[7] Dalfó, C.; Fiol, M. A.; Širáň, J., The spectra of lifted digraphs, J. Algebraic Comb., 50, 419-426 (2019) · Zbl 1429.05083
[8] Dalfó, C.; Fiol, M. A.; Pavlíková, S.; Širáň, J., Spectra and eigenspaces of arbitrary lifts of graphs · Zbl 1477.05103
[9] Dweighter, H., Elementary problems and solutions, problem E2569, Am. Math. Mon., 82, 10, 1010 (1975)
[10] Faber, V.; Moore, J. W.; Chen, W. Y.C., Cycle prefix digraphs for symmetric interconnection networks, Networks, 23, 641-649 (1993) · Zbl 0802.90043
[11] Gates, W. H.; Papadimitriou, C. H., Bounds for sorting by prefix reversal, Discrete Math., 27, 47-57 (1979) · Zbl 0397.68062
[12] Godsil, C. D., Algebraic Combinatorics (1993), Chapman and Hall: Chapman and Hall New York · Zbl 0814.05075
[13] Gross, J. L.; Tucker, T. W., Generating all graph coverings by permutation voltage assignments, Discrete Math., 18, 273-283 (1977) · Zbl 0375.55001
[14] Heydari, M. H.; Sudborough, I. H., On the diameter of the pancake network, J. Algorithms, 25, 67-94 (1997) · Zbl 0888.68007
[15] James, G.; Liebeck, M., Representations and Characters of Groups (2001), Cambridge Univ. Press · Zbl 0981.20004
[16] Konstantinova, E., On some structural properties of star and pancake graphs, (Information Theory, Combinatorics, and Search Theory. Information Theory, Combinatorics, and Search Theory, Lecture Notes in Comput. Sci., vol. 7777 (2013), Springer: Springer Heidelberg), 472-487 · Zbl 1377.05159
[17] Miller, M.; Širáň, J., Moore graphs and beyond: a survey of the degree/diameter problem, Electron. J. Comb., 20, 2 (2013), #DS14v2
[18] Sloane, N. J.A., The on-line encyclopedia of integer sequences, A058986 · Zbl 1044.11108
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.