Regular sets of circulant quartic graphs

Abstract

For a graph $\Gamma =(V,E)$ and nonnegative integers $a$ and $b$, a nonempty proper subset $C\subset V$ is called an $(a,b)$-regular 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$. In this paper, we study the existence of such sets in connected Cayley graph $\Gamma =\mathrm{Cay}({\mathbb{Z}}_n,S)$. We establish a necessary and sufficient condition for the existence of $(0,|S|)$-regular sets and identify additional conditions under which no such set can exist. We further prove that $(|S|,0)$-regular sets do not occur in $\Gamma$, and more generally, that no connected Cayley graph $\mathrm{Cay}(G,S)$ contains a $(1,|S|)$-regular set. As a main result, we determine the existence and nonexistence of $(a,b)$-regular sets in connected circulant quartic graphs for all possible values of $a$ and $b$.