Combinatorics

Discrete mathematics

Cayley graph

Graph

Graph power

Mathematics

Vertex-transitive graph

Algorithm

Automorphism

Hamming bound

Block code

Line graph

Linear code

Automorphism group

Perfect graph

Vertex (graph theory)

Decoding methods

SIAM Journal on Discrete Mathematics

Given a graph $\Gamma$, a subset $C$ of $V(\Gamma)$ is called a perfect code in $\Gamma$ if every vertex of $\Gamma$ is at distance no more than one to exactly one vertex in $C$, and a subset $C$ of $V(\Gamma)$ is called a total perfect code in $\Gamma$ if every vertex of $\Gamma$ is adjacent to exactly one vertex in $C$. In this paper we study perfect codes and total perfect codes in Cayley graphs, with a focus on the following themes: when a subgroup of a given group is a (total) perfect code in a Cayley graph of the group; and how to construct new (total) perfect codes in a Cayley graph from known ones using automorphisms of the underlying group. We prove several results around these questions.

Perfect Codes in Cayley Graphs