RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2016 Volume 13, Pages 1258–1270 (Mi semr748)

This article is cited in 5 papers

Discrete mathematics and mathematical cybernetics

Multiplicities of eigenvalues of the Star graph

S. V. Avgustinovicha, E. N. Khomyakovab, E. V. Konstantinovaab

a Sobolev Institute of Mathematics, pr. Koptyuga 4, 630090, Novosibirsk, Russia
b Novosibisk State University, Pirogova, 2, 630090, Novosibirsk, Russia

Abstract: 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.

UDC: 519.1

MSC: 05C25, 05E10, 05C50, 05E15

Received September 28, 2016, published December 23, 2016

Language: English

DOI: 10.17377/semi.2016.13.098



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025