|
This article is cited in 5 scientific papers (total in 6 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.
Received September 28, 2016, published December 23, 2016
Citation:
S. V. Avgustinovich, E. N. Khomyakova, E. V. Konstantinova, “Multiplicities of eigenvalues of the Star graph”, Sib. Èlektron. Mat. Izv., 13 (2016), 1258–1270
Linking options:
https://www.mathnet.ru/eng/semr748 https://www.mathnet.ru/eng/semr/v13/p1258
|
|