Ivan Damnjanović: On cubic polycirculant nut graphs and the degrees of regular nut graphs
On cubic polycirculant nut graphs and the degrees of regular nut graphs
Ivan Damnjanović
(This is a joint work with Nino Bašić and Patrick W. Fowler.)
Abstract: 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.