Subgroup perfect codes in Cayley graphs

Abstract

Let $\Gamma$ be a graph with vertex set $V(\Gamma )$. A subset $C$ of $V(\Gamma )$ is called a perfect code in $\Gamma$ if $C$ is an independent set of $\Gamma$ and every vertex in $V(\Gamma )\setminus C$ is adjacent to exactly one vertex in $C$. A subset $C$ of a group $G$ is called a perfect code of $G$ if there exists a Cayley graph of $G$ which admits $C$ as a perfect code. A group $G$ is said to be code-perfect if every proper subgroup of $G$ is a perfect code of $G$. In this paper we prove that a group is code-perfect if and only if it has no elements of order $4$. We also prove that a proper subgroup $H$ of an abelian group $G$ is a perfect code of $G$ if and only if the Sylow $2$-subgroup of $H$ is a perfect code of the Sylow $2$-subgroup of $G$. This reduces the problem of determining when a given subgroup of an abelian group is a perfect code to the case of abelian $2$-groups. Finally, we determine all subgroup perfect codes in any generalized quaternion group.

This is the final version to be published in SIAM Journal on Discrete Mathematics, 18 pp