2015/02/28 by Sanming Zhou
Computer Science · Engineering · Mathematics · #Cayley graph #Coding theory and cryptography #Combinatorics #Discrete mathematics #Euler's formula #Euler's totient function #Graph #Ideal (ethics) #Interconnection Networks and Systems #Mathematics #Ramanujan's sum #graph theory and CDMA systems #math.CO #msc:05C25 #msc:68M10 #msc:94A99
paper · pdf · doi:10.1016/j.jpaa.2018.05.007
Journal of Pure and Applied Algebra, 2018
openalex publication_date 2018/05/24 · arxiv created 2018/09/26 · arxiv updated 2018/09/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study two families of cyclotomic graphs and perfect codes in them. They are Cayley graphs on the additive group of ℤ[ζm]/A, with connection sets \± (ζmi + A): 0 ≤ i ≤ m-1\ and \± (ζmi + A): 0 ≤ i ≤ ϕ(m) - 1\, respectively, where ζm (m ≥ 2) is an mth primitive root of unity, A a nonzero ideal of ℤ[ζm], and ϕ Euler's totient function. We call them the mth cyclotomic graph and the second kind mth cyclotomic graph, and denote them by Gm(A) and G^*m(A), respectively. We give a necessary and sufficient condition for D/A to be a perfect t-code in G^*m(A) and a necessary condition for D/A to be such a code in Gm(A), where t ≥ 1 is an integer and D an ideal of ℤ[ζm] containing A. In the case when m = 3, 4, Gm((α)) is known as an Eisenstein-Jacobi and Gaussian networks, respectively, and we obtain necessary conditions for (β)/(α) to be a perfect t-code in Gm((α)), where 0 ≠ α, β∈ ℤ[ζm] with β dividing α. In the literature such conditions are known to be sufficient when m=4 and m=3 under an additional condition. We give a classification of all first kind Frobenius circulants of valency 2p and prove that they are all pth cyclotomic graphs, where p is an odd prime. Such graphs belong to a large family of Cayley graphs that are efficient for routing and gossiping.