SPECTRA OF CAYLEY GRAPHS

By a result of L. Lovász, the determination of the spectrum of any graph with transitive automorphism group easily reduces to that of some Cayley graph. We derive an expression for the spectrum of the Cayley graph X(G,H) in terms of irreducible characters of the group G: λti,1+...+λti,n= ∑ g1,...,gt∈HXi Π s=1 tgs for any natural number t, where ξi is an irreducible character (over C), of degree ni, and λi,1,..., λi,n are eigenvalues of X(G, H), each one ni times. (σ ni2 = n = | G | is the total'number of eigenvalues.) Using this formula for t = 1,..., ni one can obtain a polynomial of degree ni whose roots are λi,1,...,λi,n. The results are formulated for directed graphs with colored edges. We apply the results to dihedral groups and prove the existence of k nonisomorphic Cayley graphs of Dp with the same spectrum provided p > 64k, prime. © 1979.