Longest Induced Cycles on Cayley Graphs

Details Longest Induced Cycles on Cayley Graphs Longest Induced Cycles on Cayley Graphs

2004-10-13

arxiv.org/abs/math/0410308v2

Mathematics

Combinatorics

16 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Longest Induced Cycles on Cayley Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Longest Induced Cycles on Cayley Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Longest Induced Cycles on Cayley Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-136716