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: Longest Induced Cycles in Circulant Graphs. | Longest Induced Cycles in Circulant Graphs Elena D. Fuchs Department of Mathematics University of California Berkeley Berkeley CA lenfuchs@ Submitted Aug 19 2004 Accepted Jun 13 2005 Published Oct 13 2005 Mathematics Subject Classifications 05C88 05C89 Abstract In this paper we study the length of the longest induced cycle in the unit circulant graph Xn Cay zn zn where zn is the group of units in zn. Using residues modulo the primes dividing n we introduce a representation of the vertices that reduces the problem to a purely combinatorial question of comparing strings of symbols. This representation allows us to prove that the multiplicity of each prime dividing n and even the value of each prime if sufficiently large has no effect on the length of the longest induced cycle in Xn. We also see that if n has r distinct prime divisors Xn always contains an induced cycle of length 2r 2 improving the r ln r lower bound of Berrezbeitia and Giudici. Moreover we extend our results for Xn to conjunctions of complete kj-partite graphs where ki need not be finite and also to unit circulant graphs on any quotient of a Dedekind domain. 1 Introduction For a positive integer n let the unit circulant graph Xn Cay zn zn be defined as follows 1 The vertex set of Xn denoted by V n is zn the ring of integers modulo n. 2 The edge set of Xn is denoted by E n and for x y 2 V n x y 2 E n if and only if x y 2 zn where zn is the set of units in the ring Zn. The central problem adressed in this paper is to find the length of the longest induced cycle in Xn. This problem was first considered by Berrizbeitia and Giudici 1 who were motivated by its applications to chromatic uniqueness. Throughout the paper we let n la Pa2 -par where the pi are distinct primes and ai 1. Then we denote the length of the longest induced cycle in Xn by m n . We let M r maxn m n where the maximum is taken over all n with r distinct prime divisors. In 1 Berrizbeitia and Giudici bound M r by r ln r M r 9r
