Geodesic
Multiplicities of eigenvalues of the Star graph
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 1258-1270.

Voir la notice de l'article provenant de la source Math-Net.Ru

The Star graph $S_n$, $n\geqslant 2$, is the Cayley graph on the symmetric group $\mathrm{Sym}_n$ generated by the set of transpositions [4] $\{(1~2), (1~3), \ldots, (1~n)\}$. We consider the spectrum of the Star graph as the spectrum of its adjacency matrix. It is known that the spectrum of $S_n$ is integral. Analytic formulas for multiplicities of eigenvalues $\pm(n-k)$ for $k = 2, 3, 4, 5$ in the Star graph are given in this paper. We also prove that any fixed integer has multiplicity at least $2^{\frac{1}{2}n \log n (1-o(1))}$ as an eigenvalue of $S_n$.
Keywords: Cayley graph, Star graph, symmetric group, graph spectrum, eigenvalues, multiplicity. 
@article{SEMR_2016_13_a66,
     author = {S. V. Avgustinovich and E. N. Khomyakova and E. V. Konstantinova},
     title = {Multiplicities of eigenvalues of the {Star} graph},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1258--1270},
     publisher = {mathdoc},
     volume = {13},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2016_13_a66/}
}
TY  - JOUR
AU  - S. V. Avgustinovich
AU  - E. N. Khomyakova
AU  - E. V. Konstantinova
TI  - Multiplicities of eigenvalues of the Star graph
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2016
SP  - 1258
EP  - 1270
VL  - 13
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2016_13_a66/
LA  - en
ID  - SEMR_2016_13_a66
ER  - 
%0 Journal Article
%A S. V. Avgustinovich
%A E. N. Khomyakova
%A E. V. Konstantinova
%T Multiplicities of eigenvalues of the Star graph
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2016
%P 1258-1270
%V 13
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2016_13_a66/
%G en
%F SEMR_2016_13_a66
S. V. Avgustinovich; E. N. Khomyakova; E. V. Konstantinova. Multiplicities of eigenvalues of the Star graph. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 1258-1270. http://geodesic.mathdoc.fr/item/SEMR_2016_13_a66/

[1] A. Abdollahi, E. Vatandoost, Which Cayley graphs are integral?, Electron. J. Comb., 16:1 (2009), #122, 17 pp. | MR | Zbl

[2] S. B. Akers, B. Krishnamurthy, “A group-theoretic model for symmetric interconnection networks”, IEEE Trans. Comput., 38:4 (1989), 555–566 | DOI | MR | Zbl

[3] A. E. Brouwer, W. H. Haemers, Spectra of Graphs, Springer, New York, 2012 | MR | Zbl

[4] G. Chapuy, V. Féray, A note on a Cayley graph of $\mathfrak{S}_n$, 2012, arXiv: 1202.4976v2

[5] J. S. Frame, G. de B. Robinson, R. M. Thrall, “The hook graphs of the symmetric group”, Can. J. Math., 6 (1954), 316–324 | DOI | MR | Zbl

[6] J. S. Jwo, S. Lakshmivarahan, S. K. Dhall, “Embedding of cycles and grids in star graphs”, J. Circuits Syst. Comput., 1:1 (1991), 43–74 | DOI

[7] E. N. Khomyakova, E. V. Konstantinova, “Note on exact values of multiplicities of eigenvalues of the Star graph”, Sib. Electron. Math. Reports, 12 (2015), 92–100 | Zbl

[8] V. L. Kompel'makher, V. A. Liskovets, “Successive generation of permutations by means of a transposition basis”, Kibernetika, 1975, no. 3, 17–21 (in Russian) | MR | Zbl

[9] R. Krakovski, B. Mohar, “Spectrum of Cayley graphs on the symmetric group generated by transpositions”, Linear Algebra Appl., 437:3 (2012), 1033–1039 | DOI | MR | Zbl

[10] B. E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd ed., Springer, New York, 2001 | MR | Zbl

[11] P. J. Slater, “Generating all permutations by graphical transpositions”, Ars Comb., 5 (1978), 219–225 | MR | Zbl

[12] Sequence A000041, The On-Line Encyclopedia of Integer Sequences https://oeis.org/A000041