Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Integral Cayley graphs over abelian groups. | Integral Cayley graphs over abelian groups Walter Klotz and Torsten Sander Institut fur Mathematik Technische Universitat Clausthal Germany klotz@ Submitted Dec 8 2009 Accepted May 20 2010 Published May 25 2010 Mathematics Subject Classification 05C25 05C50 Abstract Let r be a finite additive group S c r 0 E S S s s E S S. The undirected Cayley graph Cay r S has vertex set r and edge set a b a b E r a b E S . A graph is called integral if all of its eigenvalues are integers. For an abelian group r we show that Cay r S is integral if S belongs to the Boolean algebra B r generated by the subgroups of r. The converse is proven for cyclic groups. A finite group r is called Cayley integral if every undirected Cayley graph over r is integral. We determine all abelian Cayley integral groups. 1 Introduction Eigenvalues of an undirected graph G are the eigenvalues of an arbitrary adjacency matrix of G. Harary and Schwenk 9 defined G to be integral if all of its eigenvalues are integers. Since then many integral graphs have been discovered for a survey see 4 . Nevertheless as is shown in 2 the probability of a labeled graph on n vertices to be integral is at most 2-n 400 for sufficiently large n. Known characterizations of integral graphs are restricted to certain graph classes. Here we proceed towards a characterization of integral Cayley graphs over abelian groups. Let r be a finite additive group S c r 0 E S S s s E S S. The undirected Cayley graph Cay r S has vertex set r. Vertices a b E r are adjacent if a b E S. For general properties of Cayley graphs we refer to Godsil and Royle 8 or Biggs 5 . Abdollahi and Vatandoost 1 show that there are exactly seven connected cubic integral Cayley graphs. So 15 presents a characterization of integral circulant graphs which are Cayley graphs over cyclic groups. In this paper we prove for an abelian group r that Cay r S is integral if S belongs to the Boolean algebra B r .
