On cubic polycirculant nut graphs and the degrees of regular 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 verify that there is no cubic 1-circulant nut graph or cubic 2-circulant nut graph, while the full classification of cubic 3-circulant nut graphs was recently obtained [Electron. J. Comb. 31(2) (2024), #2.31]. Here, we investigate the existence of cubic ℓ-circulant nut graphs for ℓ ≥ 4 and show that there is no cubic ℓ-circulant nut graph for ℓ ∈ {4, 5}, while there are infinitely many cubic ℓ-circulant nut graphs for each ℓ ∈ {6, 7} or ℓ ≥ 9. We also prove that there are infinitely many d-regular nut graphs for each d ≥ 3.

This is a joint work with Nino Bašić and Patrick W. Fowler.