Existence of regular sets in circulant quartic graphs: a complete characterization

Abstract

Let $\Gamma =(V,E)$ be a graph and let $a,b$ be nonnegative integers. A nonempty proper subset $C\subset V$ is an \emph{$(a,b)$-regular set} if each vertex of $C$ has exactly $a$ neighbors in $C$ and each vertex outside $C$ has exactly $b$ neighbors in $C$. Perfect codes and total perfect codes are the $(0,1)$- and $(1,1)$-regular sets. For every connected circulant quartic graph $\mathrm{Cay}({\mathbb{Z}}_n,\{x^{\pm k},x^{\pm \ell }\})$ and every pair $(a,b)$ we decide, in terms of $n$, $k$ and $\ell$, whether an $(a,b)$-regular set exists. Existence is proved by exhibiting unions of residue classes; non-existence comes from a Fourier-analytic obstruction combined with the fact that certain sums of roots of unity cannot vanish.