Longest induced cycles in circulant graphs

Elena D. Fuchs

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper we study the length of the longest induced cycle in the unit circulant graph Xn = 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 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 In r lower 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 unit circulant graphs on any quotient of a Dedekind domain.

Original languageEnglish (US)
JournalElectronic Journal of Combinatorics
Volume12
Issue number1 R
DOIs
StatePublished - Oct 13 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Longest induced cycles in circulant graphs'. Together they form a unique fingerprint.

Cite this