Báo cáo toán học: "A classification of Ramanujan unitary Cayley graphs"

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