Complete resolution of the circulant nut graph order-degree existence problem

MaRDI QIDQ6419720zbMATH OpenFDO

Authors Ivan Damnjanović

Publication date 6 December 2022

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Polynomials in number theory (11C08) Polynomials in real and complex fields: factorization (12D05) Polynomials, factorization in commutative rings (13P05)

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 Bav{s}i'c et al. and the first major results were obtained by Damnjanovi'c and Stevanovi'c, who proved that for each odd $tge3$ such that $totequi{v}_{10}1$ and $totequi{v}_{18}15$, there exists a $4t$-regular circulant nut graph of order $n$ for each even $nge4t+4$. Afterwards, Damnjanovi'c 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 $nge4t+4$ holds, or whenever $t$ is even, $n$ is such that $nequi{v}_{4}2$, and $nge4t+6$ holds. In this paper, we extend the aforementioned results by completely resolving the circulant nut graph order-degree existence problem. In other words, we fully determine all the possible pairs $(n,d)$ for which there exists a $d$-regular circulant nut graph of order $n$.

This page was built for publication: Complete resolution of the circulant nut graph order-degree existence problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6419720)