Resolution of the circulant nut graph order–degree existence problem

A circulant nut graph is a non-trivial simple graph such that its adjacency matrix is a circulant matrix whose null space is spanned by a single vector without zero elements. Regarding these graphs, the order–degree existence problem can be thought of as the mathematical problem of determining all the possible pairs (n, d) for which there exists a d-regular circulant nut graph of order n. This problem was initiated by Bašić et al. [Art Discret. Appl. Math. 5(2) (2021) #P2.01] and the first major results were obtained by Damnjanović and Stevanović [Linear Algebra Appl. 633 (2022) 127–151], who proved that for each odd t ≥ 3 such that t ̸≡10 1 and t ̸≡18 15, there exists a 4t-regular circulant nut graph of order n for each even n ≥ 4t+4. Afterwards, Damnjanović [arXiv:2210.08334 (2022)] improved these results by showing that there necessarily exists a 4t-regular circulant nut graph of order n whenever t is odd, n is even, and n ≥ 4t + 4 holds, or whenever t is even, n is such that n ≡4 2, and n ≥ 4t + 6 holds. Finally, the aforementioned results were extended once again by Damnjanović, thus yielding a complete resolution of the circulant nut graph order–degree existence problem. In other words, all the possible pairs (n, d) for which there exists a d-regular circulant nut graph of order n are now determined.

Everyone is welcome and encouraged to attend!