Existence of Regular Nut Graphs and the Fowler Construction

Abstract

In this paper the problem of the existence of regular nut graphs is addressed. A generalization of Fowler's Construction which is a local enlargement applied to a vertex in a graph is introduced to generate nut graphs of higher order. Let $N(\rho )$ denote the set of integers $n$ such that there exists a regular nut graph of degree $\rho$ and order $n$. It is proven that $N(3)=\{12\}\cup \{2k:k\ge 9\}$ and that $N(4)=\{8,10,12\}\cup \{n:n\ge 14\}$. The problem of determining $N(\rho )$ for $\rho >4$ remains completely open.

11 pages 8 figures research paper