Complete resolution of the circulant nut graph order-degree existence problem
| Autor: | Damnjanović, Ivan |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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\v{s}i\'c et al. and the first major results were obtained by Damnjanovi\'c and Stevanovi\'c, who proved that for each odd $t \ge 3$ such that $t\not\equiv_{10}1$ and $t\not\equiv_{18}15$, there exists a $4t$-regular circulant nut graph of order $n$ for each even $n \ge 4t + 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 $n \ge 4t + 4$ holds, or whenever $t$ is even, $n$ is such that $n \equiv_4 2$, and $n \ge 4t + 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$. Comment: arXiv admin note: text overlap with arXiv:2210.08334 |
| Databáze: | arXiv |
| Externí odkaz: |
|