tailieunhanh - Báo cáo toán học: "Integral Cayley graphs defined by greatest common divisors"

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