Complete resolution of the circulant nut graph order-degree existence problem
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913879250960384 |
|---|---|
| author | Damnjanović, Ivan |
| author_facet | Damnjanović, Ivan |
| contents | 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. and the first major results were obtained by Damnjanović and Stevanović, 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ć 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_03026 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Complete resolution of the circulant nut graph order-degree existence problem Damnjanović, Ivan Combinatorics Number Theory 05C50, 11C08, 12D05, 13P05 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. and the first major results were obtained by Damnjanović and Stevanović, 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ć 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$. |
| title | Complete resolution of the circulant nut graph order-degree existence problem |
| topic | Combinatorics Number Theory 05C50, 11C08, 12D05, 13P05 |
| url | https://arxiv.org/abs/2212.03026 |