2004/10/13 by Elena Fuchs, Fuchs, Elena, Justin Sinz +1
Computer Science · Mathematics · #05C25 #05C38 #05C50 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05C25 #msc:05C38 #msc:05C50
paper · pdf · doi:10.48550/arxiv.math/0410308
16 pages
openalex publication_date 2004/10/13 · arxiv created 2004/12/08 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we study the length of the longest induced cycle in the unitary Cayley graph Xn = Cay(\mathbb Zn; Un), where Un is the group of units in \mathbb 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 bound of Berrezbeitia and Giudici. Moreover, we extend our results for Xn to conjunctions of complete ki-partite graphs, where ki need not be finite, and also to unitary Cayley graphs on any quotient of a Dedekind domain.