ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P4.03
https://doi.org/10.26493/1855-3974.3009.6df
(Also available at http://amc-journal.eu)
Complete resolution of the circulant nut graph
order–degree existence problem
Ivan Damnjanović *
University of Niš, Faculty of Electronic Engineering,
Aleksandra Medvedeva 14, 18106 Niš, Serbia and
Diffine LLC, 3681 Villa Terrace, San Diego, CA 92104, USA
Received 20 November 2022, accepted 28 September 2023, published online 23 September 2024
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 math-
ematical 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 ≥ 3 such that t ̸≡10 1 and t ̸≡18 15, there exists a 4t-regular circulant nut graph
of order n for each even n ≥ 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 ≥ 4t + 4 holds, or whenever t is even, n is such that n ≡4 2,
and n ≥ 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.
Keywords: Circulant graph, nut graph, graph spectrum, graph eigenvalue, cyclotomic polynomial.
Math. Subj. Class. (2020): 05C50, 11C08, 12D05, 13P05
*The author is supported by Diffine LLC.
E-mail addresses: ivan.damnjanovic@elfak.ni.ac.rs (Ivan Damnjanović)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P4.03
https://doi.org/10.26493/1855-3974.3009.6df
(Dostopno tudi na http://amc-journal.eu)
Popolna rešitev problema reda in stopnje
cirkulantnega jedrnega grafa
Ivan Damnjanović *
University of Niš, Faculty of Electronic Engineering,
Aleksandra Medvedeva 14, 18106 Niš, Serbia and
Diffine LLC, 3681 Villa Terrace, San Diego, CA 92104, USA
Prejeto 20. novembra 2022, sprejeto 28. septembra 2023, objavljeno na spletu 23. septembra 2024
Povzetek
Cirkulantni jedrni graf je netrivialni enostavni graf, katerega matrika sosednosti je
cirkulantna matrika, njen ničelni prostor pa je razpet na en sam vektor brez ničelnih kom-
ponent. V zvezi s temi grafi si lahko problem reda in stopnje predstavimo kot matematični
problem določanja vseh možnih parov (n, d), za katere obstaja d-regularen cirkulanten je-
drni graf reda n. Ta problem so začeli Bašić in dr., prve pomembne rezultate pa sta dobila
Damnjanović in Stevanović, ki sta dokazala, da za vsak lih t ≥ 3 tak da t ̸≡10 1 in t ̸≡18 15,
obstaja 4t-regularen cirkulanten jedrni graf reda n za vsako sodo število n ≥ 4t+ 4. Kas-
neje je Damnjanović izboljšal te rezultate in pokazal, da zagotovo obstaja 4t-regularen
cirkulanten jedrni graf reda n, kadarkoli je t lih, n pa sod, in velja n ≥ 4t+4, ali kadarkoli
je t sod, n pa tak, da velja n ≡4 2 in n ≥ 4t + 6. V tem članku razširimo prej omenjene
rezultate in popolnoma rešimo eksistenčni problem reda in stopnje za cirkulantne jedrne
grafe. Z drugimi besedami, v celoti določimo vse možne pare (n, d), za katere obstaja
d-regularen cirkulanten jedrni graf reda n.
Ključne besede: Cirkulantni graf, jedrni graf, spekter grafa, lastna vrednost grafa, ciklotomski poli-
nom.
Math. Subj. Class. (2020): 05C50, 11C08, 12D05, 13P05
*Avtorja podpira Diffine LLC.
E-poštni naslovi: ivan.damnjanovic@elfak.ni.ac.rs (Ivan Damnjanović)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/