Spectra of Cayley graphs

Abstract

Let $G$ be a group and $S\subseteq G$ its subset such that $S=S^{-1}$, where $S^{-1}=\{s^{-1}\mid s\in S\}$. Then {\it the Cayley graph $\mathrm{Cay}(G,S)$} is an undirected graph $\Gamma$ with the vertex set $V(\Gamma )=G$ and the edge set $E(\Gamma )=\{(g,gs)\mid g\in G,s\in S\}$. A graph $\Gamma$ is said to be {\it integral} if every eigenvalue of the adjacency matrix of $\Gamma$ is integer. In the paper, we prove the following theorem: {\it if a subset $S=S^{-1}$ of $G$ is normal and $s\in S\Rightarrow s^k\in S$ for every $k\in \mathbb{Z}$ such that $(k,|s|)=1$, then $\mathrm{Cay}(G,S)$ is integral.} In particular, {\it if $S\subseteq G$ is a normal set of involutions, then $\mathrm{Cay}(G,S)$ is integral.} We also use the theorem to prove that {\it if $G=A_n$ and $S=\{(12i{)}^{\pm 1}\mid i=3,\dots ,n\}$, then $\mathrm{Cay}(G,S)$ is integral.} Thus, we give positive solutions for both problems 19.50(a) and 19.50(b) in "Kourovka Notebook".

in Russian