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 defined by greatest common divisors. | Integral Cayley graphs defined by greatest common divisors Walter Klotz Institut fur Mathematik Technische Universitat Clausthal Germany klotz@ Torsten Sander Fakultat fur Informatik Ostfalia Hochschule fur angewandte Wissenschaften Germany Submitted Dec 6 2010 Accepted Apr 12 2011 Published Apr 21 2011 Mathematics Subject Classification 05C25 05C50 Abstract An undirected graph is called integral if all of its eigenvalues are integers. Let r Zmi G G Zmr be an abelian group represented as the direct product of cyclic groups Zmi of order mi such that all greatest common divisors gcd mi mj 2 for i j. We prove that a Cayley graph Cay r S over r is integral if and only if S c r belongs to the the Boolean algebra B r generated by the subgroups of r. It is also shown that every S G B r can be characterized by greatest common divisors. 1 Introduction The greatest common divisor of nonnegative integers a and b is denoted by gcd a b . Let us agree upon gcd 0 b b. If x x1 . xr and m m1 . mr are tuples of nonnegative integers then we set gcd x m d1 . dr d di gcd xi mi for i 1 . r. For an integer n 1 we denote by Zn the additive group respectively the ring of integers modulo n Zn 0 1 . n 1 as a set. Let r be an additive abelian group represented as a direct product of cyclic groups. r Zmi G G Zmr mi 1 for i 1 . r THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P94 1 Suppose that dị is a divisor of mi 1 di mi for i 1 . r. For the divisor tuple d di . dr of m mi . mr we define the gcd-set of r with respect to d Sr d x x1 . xr G T gcd x m d . If D d 1 . d k is a set of divisor tuples of m then the gcd-set of r with respect to D is k Sr D u S d . j i In Section 2 we realize that the gcd-sets of r constitute a Boolean subalgebra Bgcd r of the Boolean algebra B r generated by the subgroups of r. The finite abelian group r is called a gcd-group if Bgcd r B r . We show that r is a gcd-group if and only if it is cyclic or isomorphic to a group of