tailieunhanh - Báo cáo toán học: "Some properties of unitary Cayley graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Some properties of unitary Cayley graphs. | Some properties of unitary Cayley graphs Walter Klotz and Torsten Sander Institut far Mathematik Technische Universitat Clausthal Germany klotz@ Submitted Feb 21 2007 Accepted May 25 2007 Published Jun 21 2007 Mathematics Subject Classification 05C25 05C50 Abstract The unitary Cayley graph Xn has vertex set Zn 0 1 . n 1g. Vertices a b are adjacent if gcd a b n 1. For Xn the chromatic number the clique number the independence number the diameter and the vertex connectivity are determined. We decide on the perfectness of Xn and show that all nonzero eigenvalues of Xn are integers dividing the value n of the Euler function. 1 Introduction Let r be a multiplicative group with identity 1. For S c r 1 2 S and S-1 s-1 s 2 Sg S the Cayley Graph X Cay r S is the undirected graph having vertex set V X r and edge set E X a bg ab 1 2 Sg. By right multiplication r may be considered as a group of automorphisms of X acting transitively on V X . The Cayley graph X is regular of degree S . Its connected components are the right cosets of the subgroup generated by S. So X is connected if S generates r. More information about Cayley graphs can be found in the books on algebraic graph theory by Biggs 3 and by Godsil and Royle 10 . For a positive integer n 1 the unitary Cayley graph Xn Cay Zn Un is defined by the additive group of the ring Zn of integers modulo n and the multiplicative group Un of its units. If we represent the elements of Zn by the integers 0 1 . n 1 then it is well known 13 that Un a 2 Zn gcd a n 1g. So Xn has vertex set V Xn Zn 0 1 . n 1 and edge set E Xn a bg a b 2 Zn gcd a - b n 1g. The graph Xn is regular of degree Un n where n denotes the Euler function. If n p is a prime number then Xn Kp is the complete graph on p vertices. If n p is a THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R45 1 prime power then Xn is a complete p-partite graph which has the residue classes modulo p in Zn as maximal sets of .