Paperlane

no. 5 · Friday 30 October 2026

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

A. Abdollahi, J. Bagherian, F. Jafari, M. Khatami, Z. Shokoohi and R. Sobhani

math.CO · v2

Abstract

Let $Γ=(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 $\operatorname{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.

fields
Combinatorics
pdf ↗ page arXiv:2609.09414 ↗