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

arXiv:2609.09414 · math.CO · Submitted 2026-09-08 · Read on arXiv

math.CO

Submitted: 2026-09-08

Updated: 2026-10-27

License: http://creativecommons.org/licenses/by/4.0/

The gist: Let Γ=(V,E) be a graph and let a,b be nonnegative integers.

Terminology

Abstract

Let Γ=(V,E) be a graph and let a,b be nonnegative integers. A nonempty proper subset C V is an(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 Cay(Z n,x plus or minus k,x plus or minus) and every pair (a,b) we decide, in terms of n, k and, 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.

Sources

Related papers