Two families of circulant nut graphs

Abstract

A circulant nut graph is a non-trivial simple graph whose adjacency matrix is a circulant matrix of nullity one such that its non-zero null space vectors have no zero elements. The study of circulant nut graphs was originally initiated by Bašić et al. [Art Discrete Appl. Math. 5(2) (2021) #P2.01], where a conjecture was made regarding the existence of all the possible pairs $(n,d)$ for which there exists a $d$-regular circulant nut graph of order $n$. Later on, it was proved by Damnjanović and Stevanović [Linear Algebra Appl. 633 (2022) 127-151] that for each odd $t\ge 3$ such that $t/{\equiv }_{10}1$ and $t/{\equiv }_{18}15$, the $4t$-regular circulant graph of order $n$ with the generator set $\{1,2,3,\dots ,2t+1\}\setminus \{t\})$ must necessarily be a nut graph for each even $n\ge 4t+4$. In this paper, we extend these results by constructing two families of circulant nut graphs. The first family comprises the $4t$-regular circulant graphs of order $n$ which correspond to the generator sets $\{1,2,\dots ,t-1\}\cup \left\{\frac{n}{4},\frac{n}{4}+1\right\}\cup \left\{\frac{n}{2}-(t-1),\dots ,\frac{n}{2}-2,\frac{n}{2}-1\right\}$, for each odd $t\in \mathbb{N}$ and $n\ge 4t+4$ divisible by four. The second family consists of the $4t$-regular circulant graphs of order $n$ which correspond to the generator sets $\{1,2,\dots ,t-1\}\cup \left\{\frac{n+2}{4},\frac{n+6}{4}\right\}\cup \left\{\frac{n}{2}-(t-1),\dots ,\frac{n}{2}-2,\frac{n}{2}-1\right\}$, for each $t\in \mathbb{N}$ and $n\ge 4t+6$ such that $n{\equiv }_{4}2$. We prove that all of the graphs which belong to these families are indeed nut graphs, thereby fully resolving the $4t$-regular circulant nut graph order-degree existence problem whenever $t$ is odd and partially solving this problem for even values of $t$ as well.

Cited by in corpus (4)

• Complete resolution of the circulant nut graph order-degree existence problem
• Classification of cubic tricirculant nut graphs
• On cubic polycirculant nut graphs
• Nut graphs with a prescribed number of vertex and edge orbits