RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2016, том 13, страницы 1258–1270 (Mi semr748)

Эта публикация цитируется в 5 статьях

Дискретная математика и математическая кибернетика

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

Аннотация: 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$.

Ключевые слова: Cayley graph, Star graph, symmetric group, graph spectrum, eigenvalues, multiplicity.

УДК: 519.1

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

Поступила 28 сентября 2016 г., опубликована 23 декабря 2016 г.

Язык публикации: английский

DOI: 10.17377/semi.2016.13.098



Реферативные базы данных:


© МИАН, 2024