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(ρ) denote the set of integers n such that there exists a regular nut graph of degree ρ and order n. It is proven that N(3) = {12} ∪ {2k : k ≥ 9} and that N(4) = {8, 10, 12} ∪ {n : n ≥ 14}. The problem of determining N(ρ) for ρ > 4 remains completely open.