Back to Search
Start Over
On regular sets in Cayley graphs
- Source :
- Journal of Algebraic Combinatorics 59 (2024) 735--759
- Publication Year :
- 2023
-
Abstract
- Let $\Ga = (V, E)$ be a graph and $a, b$ nonnegative integers. An $(a, b)$-regular set in $\Ga$ is a nonempty proper subset $D$ of $V$ such that every vertex in $D$ has exactly $a$ neighbours in $D$ and every vertex in $V \setminus D$ has exactly $b$ neighbours in $D$. A $(0,1)$-regular set is called a perfect code, an efficient dominating set, or an independent perfect dominating set. A subset $D$ of a group $G$ is called an $(a,b)$-regular set of $G$ if it is an $(a, b)$-regular set in some Cayley graph of $G$, and an $(a, b)$-regular set in a Cayley graph of $G$ is called a subgroup $(a, b)$-regular set if it is also a subgroup of $G$. In this paper we study $(a, b)$-regular sets in Cayley graphs with a focus on $(0, k)$-regular sets, where $k \ge 1$ is an integer. Among other things we determine when a non-trivial proper normal subgroup of a group is a $(0, k)$-regular set of the group. We also determine all subgroup $(0, k)$-regular sets of dihedral groups and generalized quaternion groups. We obtain necessary and sufficient conditions for a hypercube or the Cartesian product of $n$ copies of the cycle of length $p$ to admit $(0, k)$-regular sets, where $p$ is an odd prime. Our results generalize several known results from perfect codes to $(0, k)$-regular sets.<br />Comment: 27 pages
- Subjects :
- Mathematics - Combinatorics
05C25, 05C69, 94B25
Subjects
Details
- Database :
- arXiv
- Journal :
- Journal of Algebraic Combinatorics 59 (2024) 735--759
- Publication Type :
- Report
- Accession number :
- edsarx.2310.01793
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1007/s10801-024-01298-y