Vertex-transitive nut graph order-degree existence problem

Abstract

A nut graph is a nontrivial simple graph whose adjacency matrix has a simple eigenvalue zero such that the corresponding eigenvector has no zero entries. It is known that the order $n$ and degree $d$ of a vertex-transitive nut graph satisfy $4\mid d$, $d\ge 4$, $2\mid n$ and $n\ge d+4$; or $d\equiv 2(\mathrm{mod}4)$, $d\ge 6$, $4\mid n$ and $n\ge d+6$. Here, we prove that for each such $n$ and $d$, there exists a $d$-regular Cayley nut graph of order $n$. As a direct consequence, we obtain all the pairs $(n,d)$ for which there is a $d$-regular vertex-transitive (resp. Cayley) nut graph of order $n$.