Back to Search
Start Over
Regular sets in Cayley graphs
- Publication Year :
- 2020
-
Abstract
- In a graph $\Gamma$ with vertex set $V$, a subset $C$ of $V$ is called an $(a,b)$-perfect set if every vertex in $C$ has exactly $a$ neighbors in $C$ and every vertex in $V\setminus C$ has exactly $b$ neighbors in $C$, where $a$ and $b$ are nonnegative integers. In the literature $(0,1)$-perfect sets are known as perfect codes and $(1,1)$-perfect sets are known as total perfect codes. In this paper we prove that, for any finite group $G$, if a non-trivial normal subgroup $H$ of $G$ is a perfect code in some Cayley graph of $G$, then it is also an $(a,b)$-perfect set in some Cayley graph of $G$ for any pair of integers $a$ and $b$ with $0\leqslant a\leqslant|H|-1$ and $0\leqslant b\leqslant |H|$ such that $\gcd(2,|H|-1)$ divides $a$. A similar result involving total perfect codes is also proved in the paper.<br />Comment: 12 pages
- Subjects :
- Mathematics - Combinatorics
05C25, 05E18, 94B25
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2006.05100
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1007/s10801-022-01181-8.