Integral Cayley Graphs

Abstract

Let G be a group and S ⊆ G a subset such that S = S⁻¹, where S⁻¹ = {s⁻¹ | s ∈ S}. Then a Cayley graph Cay(G, S) is an undirected graph Γ with vertex set V (Γ) = G and edge set E(Γ) = {(g, gs) | g ∈ G, s ∈ S}. For a normal subset S of a finite group G such that s ∈ S ⇒ s^k ∈ S for every k ∈ ℤ which is coprime to the order of s, we prove that all eigenvalues of the adjacency matrix of Cay(G, S) are integers. Using this fact, we give affirmative answers to Questions 19.50(a) and 19.50(b) in the Kourovka Notebook.