On the degrees of regular nut graphs and Cayley nut graphs

Abstract

A nut graph is a simple graph for which the adjacency matrix has a single zero eigenvalue such that all non-zero kernel eigenvectors have no zero entry. It is known that infinitely many $d$-regular nut graphs exist for $3\le d\le 12$ and for $d\ge 4$ such that $d\equiv 0(\mathrm{mod}4)$. Here it is shown that infinitely many $d$-regular nut graphs exist for each degree $d\ge 3$. Moreover, we prove that there are infinitely many $d$-regular Cayley nut graphs for each even $d\ge 4$. This implies that we have identified all feasible degrees $d$ for which a $d$-regular Cayley nut graph exists.

13 pages, 2 figures