{
  "id": "2310.01793",
  "version": "v1",
  "published": "2023-10-03T04:42:41.000Z",
  "updated": "2023-10-03T04:42:41.000Z",
  "title": "On regular sets in Cayley graphs",
  "authors": [
    "Xiaomeng Wang",
    "Shou-Jun Xu",
    "Sanming Zhou"
  ],
  "comment": "27 pages",
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-10-03T04:42:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C25",
      "05C69",
      "94B25"
    ],
    "keywords": [
      "regular set",
      "cayley graph",
      "non-trivial proper normal subgroup",
      "perfect code",
      "nonempty proper subset"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 27,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}