Longest Induced Cycles on Cayley Graphs

MaRDI QIDQ6474577zbMATH OpenFDO

Authors Elena Fuchs, Justin Sinz

Publication date 13 October 2004

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: 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 $rlnr$ 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.

This page was built for publication: Longest Induced Cycles on Cayley Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6474577)