I came across one problem in GTM244 about the circulant graph:

A circulant is a Cayley graph $CG(\mathbb{Z}_n,S)$, where $\mathbb{Z}_n$ is the additive group of integers modulo $n$. Let $p$ be a prime, and let $i$ and $j$ be two nonzero elements of $\mathbb{Z}_p$.Determine when $CG(\mathbb{Z}_p,\{1,-1,i,-i\})\cong CG(\mathbb{Z}_p,\{1,-1,j,-j\})$

I only can show when $i\equiv\pm j$ or $ij\equiv\pm 1$, they are isomorphic but how can I find all possibilities? Intuitively, the $p$-cycle $0-1-2-\cdots-p$ and $0-i-2i-\cdots-pi$ should be mapped to $0-1-2-\cdots-p$ and $0-j-2j-\cdots-pj$ under an isomorphism.Is that the right idea? How to prove it? Thanks for any help.

  • 1
    $\begingroup$ Circulant graphs of prime order are isomorphic iff they have the same eigenvalues. And also iff one connection set is a multiple of the other mod $p$. $\endgroup$ Sep 2 at 6:48
  • $\begingroup$ I have read the related paper and got it. Thanks very much! $\endgroup$ Sep 4 at 8:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.