Two families of circulant nut graphs

Ivan Damnjanović

Filomat, Tome 37 (2023) no. 24, p. 8331

Résumé

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´Baši´c 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´cDamnjanovi´c and Stevanovi´cStevanovi´c [Linear Algebra Appl. 633 (2022) 127–151] that for each odd t ≥ 3 such that t 10 1 and t 18 15, the 4t-regular circulant graph of order n with the generator set {1, 2, 3,. .. , 2t + 1} {t}) must necessarily be a nut graph for each even n ≥ 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,. .. , t − 1} ∪ n 4 , n 4 + 1 ∪ n 2 − (t − 1),. .. , n 2 − 2, n 2 − 1 , for each odd t ∈ N and n ≥ 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,. .. , t − 1} ∪ n+2 4 , n+6 4 ∪ n 2 − (t − 1),. .. , n 2 − 2, n 2 − 1 , for each t ∈ N and n ≥ 4t + 6 such that n ≡ 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.

Détail

DOI : 10.2298/FIL2324331D

Classification : 05C50, 11C08, 12D05, 13P05
Keywords: circulant graph, nut graph, graph spectrum, graph eigenvalue, cyclotomic polynomial