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:A classification of Ramanujan unitary Cayley graphs. | A classification of Ramanujan unitary Cayley graphs Andrew Droll Submitted Sep 24 2009 Accepted May 18 2010 Published May 25 2010 Mathematics Subject Classification 05C75 Abstract The unitary Cayley graph on n vertices Xn has vertex set nz and two vertices a and b are connected by an edge if and only if they differ by a multiplicative unit modulo n . gcd a b n 1. A k-regular graph X is Ramanujan if and only if A X 2ựk 1 where A X is the second largest absolute value of the eigenvalues of the adjacency matrix of X . We obtain a complete characterization of the cases in which the unitary Cayley graph Xn is a Ramanujan graph. 1 Unitary Cayley graphs Given a finite additive abelian group G and a symmetric subset S of G we define the Cayley graph X G S to be the graph whose vertex set is G and in which two vertices v and w in G are connected by an edge if and only if v w is in S. A Cayley graph of the form X G S with G nz is called a circulant graph. The unitary Cayley graph on n vertices Xn is defined to be the undirected graph whose vertex set is nz and in which two vertices a and b are connected by an edge if and only if gcd a b n 1. This can also be stated as Xn X nz nZ where nz is the additive group of integers modulo n and nz is the set of multiplicative units modulo n. It is easy to see that Xn is a simple n -regular graph where is the Euler totient function. Here An is defined by A1 1 and for an integer n 1 with distinct prime power factorization p0 pl p for distinct primes p0 pt and nonnegative integers eo et with t 0 p n p00-1 ptt-1 po 1 pt 1 . The eigenvalues of the adjacency matrix of X G S for an abelian group G and symmetric subset S are Am Xm s 1 sES for m 0 G 1 where x0 X G -1 are the irreducible characters of G see for example Murty 2003 . We therefore have the following lemma see Klotz W. and Sander T. 2007 for example . THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N29 1 Lemma The eigenvalues of any adjacency matrix of Xn are Am n E e a a n 1
