On cubic polycirculant nut graphs

A nut graph is a nontrivial simple graph whose adjacency matrix contains a one-dimensional null space spanned by a vector without zero entries. Moreover, an ℓ -circulant graph is a graph that admits a cyclic group of automorphisms having ℓ vertex orbits of equal size. It is not difficult to observe that there exists no cubic 1-circulant nut graph or cubic 2-circulant nut graph, while the full classification of all the cubic 3-circulant nut graphs was recently obtained (Damnjanović et al. in Electron J Comb 31(2):P2.31, 2024). Here, we investigate the existence of cubic ℓ -circulant nut graphs for ≥ 4 ℓ ≥ 4 and show that there is no cubic 4-circulant nut graph or cubic 5-circulant nut graph by using a computer-assisted proof. Furthermore, we rely on a construction based approach in order to demonstrate that there exist infinitely many cubic ℓ -circulant nut graphs for any fixed ∈ \6, 7 \ ℓ ∈ { 6 , 7 } or ≥ 9 ℓ ≥ 9 .