Back to Search
Start Over
Subgroup perfect codes in Cayley graphs
- Publication Year :
- 2019
-
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.<br />Comment: This is the final version to be published in SIAM Journal on Discrete Mathematics, 18 pp
- Subjects :
- Mathematics - Combinatorics
05C25, 05C69, 94B25
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1904.01858
- Document Type :
- Working Paper