Longest Induced Cycles on Cayley Graphs
| dc.creator | Fuchs, Elena | |
| dc.creator | Sinz, Justin | |
| dc.date | 2004-10-13 | |
| dc.date | 2004-12-08 | |
| dc.date.accessioned | 2026-07-07T05:13:14Z | |
| dc.date.available | 2026-07-07T05:13:14Z | |
| dc.description | In this paper we study the length of the longest induced cycle in the unitary Cayley graph $X_n = Cay(\mathbb Z_n; U_n)$, where $U_n$ is the group of units in $\mathbb Z_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 \ln r$ 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 unitary Cayley graphs on any quotient of a Dedekind domain. | |
| dc.description | 16 pages | |
| dc.identifier | https://arxiv.org/abs/math/0410308 | |
| dc.identifier | http://arxiv.org/abs/math/0410308 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/72873 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C38; 05C25; 05C50 | |
| dc.title | Longest Induced Cycles on Cayley Graphs | |
| dc.type | text |