Ivan Damnjanović: Resolution of the circulant nut graph order - degree existence problem

Datum objave: 3. 12. 2022
Seminar za diskretno matematiko
torek
6
december
Ura:
10.15
Lokacija:
Plemljev seminar, Jadranska 19

Abstract. 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 ̸≡ 1 (mod 10) and t ̸≡15 (mod 18), 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 ≡ 2(mod 4), 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.