Complete resolution of the circulant nut graph order-degree existence problem

A circulant nut graph is a non-trivial simple graph such that its adjacency matrix is a circulant matrix whose null space is spanned by a single vector without zero elements. Regarding these graphs, the order-degree existence problem can be thought of as the mathematical problem of determining all the possible pairs $(n,d)$ for which there exists a $d$-regular circulant nut graph of order $n$. This problem was initiated by Bašić et al. and the first major results were obtained by Damnjanović and Stevanović, who proved that for each odd $t\ge 3$ such that $t\mathrm{̸}{\equiv }_{10}1$ and $t\mathrm{̸}{\equiv }_{18}15$, there exists a $4t$-regular circulant nut graph of order $n$ for each even $n\ge 4t+4$. Afterwards, Damnjanović improved these results by showing that there necessarily exists a $4t$-regular circulant nut graph of order $n$ whenever $t$ is odd, $n$ is even, and $n\ge 4t+4$ holds, or whenever $t$ is even, $n$ is such that $n{\equiv }_{4}2$, and $n\ge 4t+6$ holds. In this paper, we extend the aforementioned results by completely resolving the circulant nut graph order-degree existence problem. In other words, we fully determine all the possible pairs $(n,d)$ for which there exists a $d$-regular circulant nut graph of order $n$.