Cyclotomic graphs and perfect codes

Abstract: We study two families of cyclotomic graphs and perfect codes in them. They are Cayley graphs on the additive group of

m a t h b b Z [z e t a_{m}] / A

, with connection sets

p m (z e t a_{m}^{i} + A) : 0 l e i l e m - 1

and

p m (z e t a_{m}^{i} + A) : 0 l e i l e p h i (m) - 1

, respectively, where

z e t a_{m}

(

m g e 2

) is an

m

th primitive root of unity,

A

a nonzero ideal of

m a t h b b Z [z e t a_{m}]

, and

p h i

Euler's totient function. We call them the

m

th cyclotomic graph and the second kind

m

th cyclotomic graph, and denote them by

G_{m} (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

G_{m} (A)

, where

t g e 1

is an integer and

D

an ideal of

m a t h b b Z [z e t a_{m}]

containing

A

. In the case when

m = 3, 4

,

G_{m} ((a l p h a))

is known as an Eisenstein-Jacobi and Gaussian networks, respectively, and we obtain necessary conditions for

to be a perfect

t

-code in

G_{m} ((a l p h a))

, where

with

dividing

a l p h a

. 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

2 p

and prove that they are all

p

th 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.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Cyclotomic graphs and perfect codes