On regular sets in Cayley graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911836825190400 |
|---|---|
| author | Wang, Xiaomeng Xu, Shou-Jun Zhou, Sanming |
| author_facet | Wang, Xiaomeng Xu, Shou-Jun Zhou, Sanming |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_01793 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On regular sets in Cayley graphs Wang, Xiaomeng Xu, Shou-Jun Zhou, Sanming Combinatorics 05C25, 05C69, 94B25 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. |
| title | On regular sets in Cayley graphs |
| topic | Combinatorics 05C25, 05C69, 94B25 |
| url | https://arxiv.org/abs/2310.01793 |