On circulant nut graphs

Abstract

A nut graph is a simple graph whose adjacency matrix has the eigenvalue 0 with multiplicity 1 such that its corresponding eigenvector has no zero entries. Motivated by a question of Fowler et al. (2020) [5] to determine the pairs (n,d) for which a vertex-transitive nut graph of order n and degree d exists, Bašić et al. (2021) [1] initiated the study of circulant nut graphs. Here we first show that the generator set of a circulant nut graph necessarily contains equally many even and odd integers. Then we characterize circulant nut graphs with the generator set {x,x+1,x+2,…,x+2t−1} for x,t∈N, which generalizes the result of Bašić et al. for the generator set {1,2,3,…,2t}. We further study circulant nut graphs with the generator set {1,2,3,…,2t+1}∖{t}, which yields nut graphs of every even order n≥4t+4 whenever t is odd such that t≢101 and t≢1815. This fully resolves Conjecture 9 from Bašić et al. (2021) [1]. We also study the existence of 4t-regular circulant nut graphs for small values of t, which partially resolves Conjecture 10 of Bašić et al. (2021) [1].