Integral Cayley Graphs

A graph X is said to be integral if all eigenvalues of the adjacency matrix of X are integers. This property was first defined by Harary and Schwenk who suggested the problem of classifying integral graphs. Since the general problem of classifying integral graphs seemed too difficult, graph theorists started to investigate special classes of graphs which included trees, graphs of bounded degree, regular graphs and Cayley graphs. What proves so interesting about this problem is that no one can yet identify what the integral trees are or which 5-regular graphs are integral. In this thesis, integral Cayley graphs are studied. Several topics on the integral Cayley graphs are presented. First, a classification of integral Cayley graphs over abelian groups in terms of the associated Boolean algebra of the subgroups is presented. Secondly, the notions of character and representation integrality are introduced. It has been shown that character integrality is a weaker notion than representation integrality. An internal classification of character integral subsets is proved. General results about representation integral subsets are presented and in an attempt to generalize the results from abelian to non-abelian case, Hamiltonian and dihedral groups are studied. Thirdly, two open problems about integrality of Cayley graphs are solved. Simple eigenvalues in Cayley graphs are studied, and some observations lead to two interesting results in this topic. Finally, the classification of cubic and 4-regular integral Cayley graphs are presented. A general approach to characterize all integral Cayley graphs over abelian groups is presented. Furthermore, a sharp upper bound over the size of the group in terms of the graph degree has been suggested and proved. The thesis concludes with a section devoted to open problems and conjectures in this area.