The algebraic degree of spectra of circulant graphs.

We investigate the algebraic degree of circulant graphs, i.e. the dimension of the splitting field of the characteristic polynomial of the associated adjacency matrix over the rationals. Studying the algebraic degree of graphs seems more natural than characterizing graphs with integral spectra only. We prove that the algebraic degree of circulant graphs on n vertices is bounded above by φ (n) / 2 , where φ denotes Euler's totient function, and that the family of cycle graphs provides a family of maximum algebraic degree within the family of all circulant graphs. Moreover, we precisely determine the algebraic degree of circulant graphs on a prime number of vertices. [ABSTRACT FROM AUTHOR]