Perfect codes in circulant graphs

Abstract: A perfect code in a graph

G a m m a = (V, E)

is a subset

C

of

V

that is an independent set such that every vertex in

V s e t m i n u s C

is adjacent to exactly one vertex in

C

. A total perfect code in

G a m m a

is a subset

C

of

V

such that every vertex of

V

is adjacent to exactly one vertex in

C

. A perfect code in the Hamming graph

H (n, q)

agrees with a

q

-ary perfect 1-code of length

n

in the classical setting. In this paper we give a necessary and sufficient condition for a circulant graph of degree

p - 1

to admit a perfect code, where

p

is an odd prime. We also obtain a necessary and sufficient condition for a circulant graph of order

n

and degree

p^{l} - 1

to have a perfect code, where

p

is a prime and

p^{l}

the largest power of

p

dividing

n

. Similar results for total perfect codes are also obtained in the paper.

Cites Work

Cited In (32)

This page was built for publication: Perfect codes in circulant graphs