Longest induced cycles in circulant graphs

In this paper we study the length of the longest induced cycle in the unit circulant graph X_n = Cay(ℤ;ℤ_n*), where ℤ* is the group of units in ℤ_n. 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 X_n. We also see that if n has r distinct prime divisors, X_n always contains an induced cycle of length 2^r + 2, improving the r In r lower bound of Berrezbeitia and Giudici. Moreover, we extend our results for X_n to conjunctions of complete k_i-partite graphs, where k_i need not be finite, and also to unit circulant graphs on any quotient of a Dedekind domain.