Ac
ce
pt
ed
 m
an
us
cr
ip
tISSN 2590-9770
The Art of Discrete and Applied Mathematics
https://doi.org/10.26493/2590-9770.1403.1b1
(Also available at http://adam-journal.eu)
On 12-regular nut graphs∗
Nino Bašić †
FAMNIT & IAM, University of Primorska, 6000 Koper, Slovenia, and
Institute of Mathematics, Physics and Mechanics, 1000 Ljubljana, Slovenia
Martin Knor ‡
Department of Mathematics, Faculty of Civil Engineering, Slovak University of
Technology in Bratislava, Radlinského 11, 810 05, Bratislava, Slovakia
Riste Škrekovski §
Faculty of Information Studies, 8000 Novo mesto, Slovenia, and
FMF, University of Ljubljana, 1000 Ljubljana, Slovenia, and
FAMNIT, University of Primorska, 6000 Koper, Slovenia
Received 8 February 2021, accepted 29 May 2021
Abstract
A nut graph is a simple graph whose adjacency matrix is singular with 1-dimensional
kernel such that the corresponding eigenvector has no zero entries. In 2020, Fowler et al.
characterised for each d ∈ {3, 4, . . . , 11} all values n such that there exists a d-regular nut
graph of order n. In the present paper, we resolve the first open case d = 12, i.e. we show
that there exists a 12-regular nut graph of order n if and only if n ≥ 16. We also present a
result by which there are infinitely many circulant nut graphs of degree d ≡ 0 (mod 4) and
no circulant nut graphs of degree d ≡ 2 (mod 4). The former result partially resolves a
question by Fowler et al. on existence of vertex-transitive nut graphs of order n and degree
d. We conclude the paper with problems, conjectures and ideas for further work.
Keywords: Nut graph, adjacency matrix, singular matrix, core graph, Fowler construction, regular
graph.
Math. Subj. Class.: 05C50, 15A18
∗We would like to thank the two anonymous referees for their comments which helped to improve the presen-
tation of the paper.
†The work of the first author is supported in part by the Slovenian Research Agency (research program P1-
0294 and research projects J1-9187, J1-1691, N1-0140 and J1-2481).
‡The second author acknowledges partial support by Slovak research grants APVV-15-0220, APVV-17-0428,
VEGA 1/0206/20 and VEGA 1/0238/19.
§The research of the third author was partially supported by the Slovenian Research Agency (ARRS), research
program P1-0383 and research projects J1-1692 and J1-8130.
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
Ac
ce
pt
ed
 m
an
us
cr
ip
t
2 Art Discrete Appl. Math.
1 Introduction
Let G be a simple graph with the vertex set V (G) = {0, 1, . . . , n−1}. Its adjacency matrix
A is a symmetric n×nmatrix with entries ai,j , where 0 ≤ i, j ≤ n−1, such that ai,j = 1 if
{i, j} is an edge of G and ai,j = 0 otherwise. A graph G is a nut graph if A has eigenvalue
0 and no eigenvector has zero entries. As a consequence, the eigenspace corresponding
to the eigenvalue 0 is 1-dimensional. Observe that if the eigenspace corresponding to 0
has dimension greater than one, then there exists an eigenvector containing entry 0 that is
different from 0 = (0, 0, . . . , 0)T . For an introductory treatment of spectral graph theory,
which links graphs to linear algebra, see e.g. [3, 4, 7].
Nut graphs have been studied in [6, 9, 11, 12, 16, 17, 18, 19, 20, 22], see also the
webpage https://hog.grinvin.org/Nuts within the House of Graphs [2, 5]. Re-
cently, this concept was extended to signed graphs [1]. Nut graphs have chemical applica-
tions, see e.g. [9, 8, 21]. However, in the present paper we consider 12-regular graphs, so
our motivation is purely mathematical.
In [22], Gutman and Sciriha showed that the smallest non-trivial nut graph has order 7.
In [10], Fowler et al. determined all nut graphs on up to 10 vertices and all chemical nut
graphs on up to 16 vertices. The smallest order for which a regular nut graph exists is 8;
see also [9]. In [9], Fowler et al. presented the following question.
If there exists a d-regular graph of order n, then we say that the order n is admissible
regarding the degree d. Obviously, if d is even then every n ≥ d + 1 is admissible. If d is
odd then every even n ≥ d+ 1 is admissible.
Question 1.1. Is it true that for each degree d ≥ 3 there are only finitely many admissible
orders n such that there does not exist a d-regular nut graph of order n?
In the attempt to answer Question 1.1, the ‘Fowler Construction’ played an important
role; see also [11]. This construction implies the following theorem.
Theorem 1.2. Let G be a nut graph on n vertices and let u be a vertex of G of degree d.
Then there exists a nut graph of order n + 2d that is obtained from G by adding 2d new
vertices and rearranging the edges in a certain way. In the newly obtained nut graph the
degrees of the new vertices are d and the degrees of the original vertices are not changed.
Obviously, if G is a d-regular graph of order n, then the new graph is d-regular of order
n + 2d. Hence, to answer Question 1.1 positively for specific degree d, it suffices to find
d-regular graphs for 2d consecutive orders. In [11] (d = 3, 4) and [9] (5 ≤ d ≤ 11), the
authors found all pairs (d, n), such that d ≤ 11 and there exists a d-regular nut graph of
order n. In the present paper, we extend this result to d = 12. We prove the following
statement.
Theorem 1.3. There exists a 12-regular nut graph of order n if and only if n ≥ 16.
To prove the ‘positive part’ of Theorem 1.3, it suffices to find 12-regular nut graphs of
orders n ∈ {16, 17, . . . , 39}. We present these graphs in the following section. For odd
orders there is not much to say; we did a computer search and thus we provide a list of
graphs that we found. However, for even orders we can say more.
E-mail addresses: nino.basic@famnit.upr.si (Nino Bašić ), knor@math.sk (Martin Knor ),
skrekovski@gmail.com (Riste Škrekovski )
Ac
ce
pt
ed
 m
an
us
cr
ip
t
N. Bašić et al.: On 12-regular nut graphs 3
A graphG is called vertex-transitive if all vertices are equivalent under the action of the
automorphism group Aut(G). In other words, for each pair of vertices u, v ∈ V (G) there
exist an automorphism α ∈ Aut(G) such that α(u) = v. In [9], the following necessary
condition for a vertex-transitive nut graph was given.
Theorem 1.4. LetG be a vertex-transitive nut graph of degree d on n vertices. Then n and
d satisfy the following conditions. Either
(1) d ≡ 0 (mod 4), n ≡ 0 (mod 2) and n ≥ d+ 4, or
(2) d ≡ 0 (mod 2), n ≡ 0 (mod 4) and n ≥ d+ 6.
The existence of vertex-transitive nut graphs is interesting in its own right, see [9, Ques-
tion 9]. For our research it is important that, by Theorem 1.4, there may exist vertex-
transitive 12-regular graphs of even orders n ≥ 16. We found such graphs among circulant
graphs.
2 Results
We start with the ‘negative part’ of Theorem 1.3. There is only one 12-regular graph of
order 13, namely the complete graph K13, and it is not a nut graph. The unique 12-regular
graph of order 14 is obtained by removing a matching from K14, and again, this graph is
not a nut graph. Finally, there are 17 graphs of order 15 which are 12-regular. They are
obtained by removing a 2-factor fromK15. Using the SageMath software [23], we analysed
all such graphs and concluded that none of them is a nut graph.
Now we turn our attention to the ‘positive part’ of Theorem 1.3. We start with more
general results for even orders. The following lemma is in fact implied in the text preceding
Proposition 1 in [11]. We present it here in a slightly more general setting together with its
short proof.
Lemma 2.1. Let G be a d-regular graph on n vertices such that its adjacency matrix A is
singular. Then for every eigenvector c = (c0, c1, . . . , cn−1)T corresponding to eigenvalue
0, we have
n−1∑
i=0
ci = 0.
Proof. In every d-regular graph, the eigenvector 1 = (1, 1, . . . , 1) corresponds to the eigen-
value d. Since eigenspaces are mutually orthogonal, we have c · 1 = 0.
Let V = {0, 1, . . . , n−1} and let 1 ≤ a1 < a2 < · · · < at ≤ n2 . By C(n, {a1, a2, . . . ,
at}) we denote a graph on the vertex set V in which two vertices i, j ∈ V are adjacent
if and only if |i − j| = ak, where 1 ≤ k ≤ t. The graph C(n, {a1, a2, . . . , at}) is
called a circulant graph and it is regular. Its degree is 2t − 1 if at = n2 and 2t otherwise.
In fact, circulant graphs are vertex-transitive since ϕ : i → i + 1 is an automorphism of
C(n, {a1, a2, . . . , at}) (the addition is modulo n).
Circulant graphs are easy to describe and easy to handle. Therefore, it would be nice
if there were many nut graphs among them. We prove one positive and one negative result
about circulant graphs. We start with the following lemma.
Lemma 2.2. Let G = C(n, {a1, a2, . . . , at}) be a circulant nut graph, and let A be its ad-
jacency matrix. Then (1,−1, 1,−1, . . . )T is an eigenvector corresponding to eigenvalue 0.
Ac
ce
pt
ed
 m
an
us
cr
ip
t
4 Art Discrete Appl. Math.
Proof. We use the well-known fact that if b and c are eigenvectors corresponding to eigen-
value λ, then b+ c is also an eigenvector corresponding to eigenvalue λ.
Let b = (b0, b1, . . . , bn−1)T be an eigenvector corresponding to 0. Denote b0 = p and
b1 = q. Since ϕ : i→ 2− i is an automorphism of G (the addition being modulo n), there
is an eigenvector c = (c0, c1, . . . , cn−1)T such that c2−i = −bi, 0 ≤ i ≤ n − 1. Then
c1 = −b1 = −q and c2 = −b0 = −p. Since b1 + c1 = 0 and b + c is an eigenvector,
we must have b + c = 0 because G is a nut graph. Hence, b2 + c2 = 0 and therefore
b2 = p. Now repeating the process we get b = (p, q, p, q, . . . ). Observe that n is even
by Theorem 1.4. Thus, by Lemma 2.1, we have q = −p and so (1,−1, 1,−1, . . . ) is an
eigenvector corresponding to eigenvalue 0.
Our negative result covers all circulant graphs of degree d ≡ 2 (mod 4).
Theorem 2.3. There is no circulant nut graph of degree d if d ≡ 2 (mod 4).
Proof. Let d ≡ 2 (mod 4). Denote t = d2 . Observe that t is an odd number. By way of
contradiction, assume that G = C(n, {a1, a2, . . . , at}) is a circulant nut graph. Then n
is even by Theorem 1.4. Let A = (a0,a1, . . . ,an−1)T be the adjacency matrix of G. By
Lemma 2.2, c = (1,−1, 1,−1, . . . )T is an eigenvector corresponding to eigenvalue 0, so
that Ac = 0, and in particular a0c = 0. However,
a0c = ca1 + ca2 + · · ·+ cat + cn−a1 + cn−a2 + · · ·+ cn−at .
Since cai = cn−ai for every i, 1 ≤ i ≤ t (observe that the difference between indices
ai and n − ai is even), we have a0c = 2(ca1 + ca2 + · · · + cat), which implies that
ca1 + ca2 + · · · + cat = 0. However, the sum of an odd number of odd numbers is odd, a
contradiction.
Now we prove the positive result. Notice that this result also partially resolves Ques-
tion 9 from [9] about the existence of vertex-transitive nut graphs of order n and degree d.
Theorem 2.4. Let d ≡ 0 (mod 4) and let n be even. Then C(n, {1, 2, . . . , d2}) is a nut
graph if and only if d2 + 1 is coprime to n and
d
4 is coprime to
n
2 .
Proof. Let t = d2 . Then t is even and the graph is G = C(n, {1, 2, . . . , t}).
Let A be the adjacency matrix of G. By Lemma 2.2, b = (1,−1, 1,−1, . . . )T is an
eigenvector of A corresponding to eigenvalue 0. Thus Ab = 0. Our aim is to show that if
t+1 is coprime to n and t2 is coprime to
n
2 , then Ac = 0 if and only if c is a multiple of b.
So let Ac = 0, where c = (c0, c1, . . . , cn−1)T . Let A = (a0,a1, . . . ,an−1)T . Then
atc = c0 + c1 + · · ·+ ct−1 + ct+1 + ct+2 + · · ·+ c2t = 0,
at+1c = c1 + c2 + · · ·+ ct + ct+2 + ct+3 + · · ·+ c2t+1 = 0.
Subtracting the two equations we get
atc− at+1c = c0 − ct + ct+1 − c2t+1 = 0,
and analogously
a2t+1c− a2t+2c = ct+1 − c2t+1 + c2t+2 − c3t+2 = 0.
Ac
ce
pt
ed
 m
an
us
cr
ip
t
N. Bašić et al.: On 12-regular nut graphs 5
This gives
c0 − ct = c2t+2 − c3t+2,
and analogously
c2t+2 − c3t+2 = c4t+4 − c5t+4,
c4t+4 − c5t+4 = c6t+6 − c7t+5, etc.
So if the odd number t+ 1 is coprime to the even number n, we get
c0 − ct = c2(t+1) − ct+2(t+1) = · · · = c2 − ct+2,
which gives
c2 − c0 = ct+2 − ct,
and analogously we get
ct+2 − ct = c2t+2 − c2t,
c2t+2 − c2t = c3t+2 − c3t, etc.
Here, t and n are both even. But if t2 is coprime to
n
2 then
c2 − c0 = ct+2 − ct = · · · = c4 − c2.
Hence,
c2 − c0 = c4 − c2 = c6 − c4 = · · ·
Now, if c2 > c0 then c0 < c2 < c4 < · · · < c0, a contradiction. Analogously, if c2 < c0
then c0 > c2 > c4 > · · · > c0, a contradiction. So c0 = c2 = · · · = cn−2 and analogously
c1 = c3 = · · · = cn−1. Hence if c0 = p, then c = (p,−p, p,−p, . . . ) by Lemma 2.1, and
the eigenspace corresponding to eigenvalue 0 is 1-dimensional.
Now suppose that t+1 is not coprime to n. Set b = 0. We will change some entries of
b. Since t+ 1 is odd, there is an even k such that (t+ 1)k ≡ 0 (mod n) and 1 ≤ k < n.
Set
b0 = 1, bt+1 = −1, b2(t+1) = 1, b3(t+1) = −1, . . . ,
where the indices are modulo n. We have changed k entries of b and since k is even, the
last changed entry has value −1. Thus some entries of b remained 0’s and nevertheless
Ab = 0, since if j-th entry of ai is 1, then either (j + (t + 1))-th or (j − (t + 1))-th
(modulo n) entry of ai is also 1 (while the other is 0). Hence, G is not a nut graph in this
case.
Finally, suppose that t2 is not coprime to
n
2 . Then there exists a number k such that
k | t2 , k |
n
2 and k > 1. Again, set b = 0. We will change some entries of b. Set
b0 = b2 = b4 = · · · = b2(k−2) = 1 and b2(k−1) = −(k − 1),
and repeat this pattern for all even indices of b. Since k | n2 , this pattern is repeated
exactly n2k times. And since every ai contains two disjoint sets of t consecutive 1’s, we
have Ab = 0. But half of the entries of b are 0’s and therefore G is not a nut graph.
Ac
ce
pt
ed
 m
an
us
cr
ip
t
6 Art Discrete Appl. Math.
Observe that the only requirement for n in Theorem 2.4 is that n is even and n > d.
However, if n = d + 2 then d2 + 1 is not coprime to n, and so n ≥ d + 4. Hence, by
Theorem 2.4, for d = 12 the following circulant graphs are nut graphs:
C(16, {1, 2, 3, 4, 5, 6}), C(20, {1, 2, 3, 4, 5, 6}), C(22, {1, 2, 3, 4, 5, 6}),
C(26, {1, 2, 3, 4, 5, 6}), C(32, {1, 2, 3, 4, 5, 6}), C(34, {1, 2, 3, 4, 5, 6}), and
C(38, {1, 2, 3, 4, 5, 6}).
Using the computer [23] we found the following graphs that are nut graphs:
C(18, {1, 2, 3, 4, 5, 8}), C(24, {1, 2, 3, 4, 5, 8}), C(28, {1, 2, 3, 4, 5, 10}),
C(30, {1, 2, 3, 4, 5, 8}), and C(36, {1, 2, 3, 4, 5, 8}).
3 Concluding remarks and further work
From the very beginning of our work on this paper, the nut circulant graphs were continu-
ously present, which fact motivates us explicitly to pose here the following problem.
Problem 3.1. Find which circulant graphs are nut graphs.
By the arguments in this paper, any circulant nut graph must satisfy the conditions of
Theorem 1.4(1), i.e. the order n is even, the degree d is divisible by 4, and n ≥ d+ 4. We
believe that for any such pairs n and d, there exists a circulant nut graph.
Conjecture 3.2. For every d, where d ≡ 0 (mod 4), and for every even n, n ≥ d + 4,
there exists a circulant nut graph C(n, {a1, a2, . . . , ad/2}) of degree d.
And, as a very particular case of the above conjecture, by restricting to 12-regular
graphs, we also propose.
Conjecture 3.3. For every even n, n ≥ 16, there exists a circulant nut graph C(n, {a1, a2,
. . . , a6}) of degree 12.
By Theorem 1.4, if n is odd then there is no vertex-transitive nut graph of order n and
degree 12. In this case all graphs were found by a computer search. If G is a regular graph
that contains edges u1v1 and u2v2 but does not contain edges u1v2, u2v1, then rewiring (i.e.
removing edges u1v1, u2v2 and adding edges u1v2, u2v1; it is also known as a Ryser switch
[15]) yields another regular graph. Our approach was to start with a ‘random’ 12-regular
graph of odd order and perform a sequence of rewirings. In this way all graphs in the
Appendix were obtained. For instance, the graph on 21 vertices, whose kernel eigenvector
contains only values 1 and −2, was obtained from C(21, {1, 2, 3, 4, 5, 6}) by removing the
edges (0, 16) and (2, 7) and adding the edges (0, 7) and (2, 16).
Note that kernel eigenvectors of all graphs in the Appendix on n = 3k vertices (for
k = 7, 9, 11, 13) contain only values 1 and −2. All those graphs have a special structure.
Let V = V1 ∪ V−2 be the partition of vertices with respect to the kernel eigenvector entry.
In each case, the graph induced by V−2 is isomorphic to a graph that can be obtained from
C(k, {1, 2}) by at most one rewiring, while the graph induced by V1 is isomorphic to a
graph that can be obtained from C(2k, {1, 2, 3, 4}) by at most one rewiring. Moreover,
let BiC(n, S) be the graph with the vertex set V = {v0, . . . , vn−1, u0, . . . , un−1} and the
edge set E = {viu(i+s) mod n : 0 ≤ i < n, s ∈ S}. This graph is a special kind of
Ac
ce
pt
ed
 m
an
us
cr
ip
t
N. Bašić et al.: On 12-regular nut graphs 7
bicirculant (see [13, 14] and references cited therein). The set V1 can be partitioned into
two subsets V1 = V ′1 ∪V ′′1 , |V ′1 | = |V ′′1 |, such that the graph induced by edges from V−2 to
V ′1 is isomorphic to a graph that can be obtained from BiC(k, {0, 1, 2, 3}) by at most one
rewiring. Similarly, the graph induced by edges from V−2 to V ′′1 is also isomorphic to a
graph that can be obtained from BiC(k, {0, 1, 2, 3}) by at most one rewiring.
ORCID iDs
Nino Bašić https://orcid.org/0000-0002-6555-8668
Martin Knor https://orcid.org/0000-0003-3555-3994
Riste Škrekovski https://orcid.org/0000-0001-6851-3214
References
[1] N. Bašić, P. W. Fowler, T. Pisanski and I. Sciriha, On singular signed graphs with nullspace
spanned by a full vector: Signed nut graphs, 2020, arXiv:2009.09018 [math.CO].
[2] G. Brinkmann, K. Coolsaet, J. Goedgebeur and H. Mélot, House of Graphs: A database of
interesting graphs, Discrete Appl. Math. 161 (2013), 311–314, doi:10.1016/j.dam.2012.07.018.
[3] A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Universitext, Springer, New York, 2012,
doi:10.1007/978-1-4614-1939-6.
[4] F. R. K. Chung, Spectral Graph Theory, volume 92 of CBMS Regional Conference Series in
Mathematics, American Mathematical Society, Providence, RI, 1997.
[5] K. Coolsaet, P. W. Fowler and J. Goedgebeur, Nut graphs, homepage of Nutgen, http://
caagt.ugent.be/nutgen/.
[6] K. Coolsaet, P. W. Fowler and J. Goedgebeur, Generation and properties of nut graphs, MATCH
Commun. Math. Comput. Chem. 80 (2018), 423–444.
[7] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications, Johann
Ambrosius Barth, Heidelberg, 3rd edition, 1995.
[8] P. W. Fowler, N. Bašić and T. Pisanski, Charting the space of chemical nut graphs, MATCH
Commun. Math. Comput. Chem. 86 (2021), 519–538.
[9] P. W. Fowler, J. B. Gauci, J. Goedgebeur, T. Pisanski and I. Sciriha, Existence of regular nut
graphs for degree at most 11, Discuss. Math. Graph Theory 40 (2020), 533–557, doi:10.7151/
dmgt.2283.
[10] P. W. Fowler, B. T. Pickup, T. Z. Todorova, M. Borg and I. Sciriha, Omni-conducting and omni-
insulating molecules, J. Chem. Phys. 140 (2014), Article No. 054115, doi:10.1063/1.4863559.
[11] J. B. Gauci, T. Pisanski and I. Sciriha, Existence of regular nut graphs and the Fowler construc-
tion, Appl. Anal. Discrete Math. (2021), doi:10.2298/aadm190517028g.
[12] I. Gutman and I. Sciriha, Graphs with maximum singularity, Graph Theory Notes N. Y. 30
(1996), 17–20.
[13] I. Kovács, B. Kuzman, A. Malnič and S. Wilson, Characterization of edge-transitive 4-valent
bicirculants, J. Graph Theory 69 (2012), 441–463, doi:10.1002/jgt.20594.
[14] A. Malnič, D. Marušič, P. Šparl and B. Frelih, Symmetry structure of bicirculants, Discrete
Math. 307 (2007), 409–414, doi:10.1016/j.disc.2005.09.033.
[15] H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Canadian J. Math. 9
(1957), 371–377, doi:10.4153/cjm-1957-044-3.
Ac
ce
pt
ed
 m
an
us
cr
ip
t
8 Art Discrete Appl. Math.
[16] I. Sciriha, On the construction of graphs of nullity one, Discrete Math. 181 (1998), 193–211,
doi:10.1016/s0012-365x(97)00036-8.
[17] I. Sciriha, A characterization of singular graphs, Electron. J. Linear Algebra 16 (2007), 451–
462, doi:10.13001/1081-3810.1215.
[18] I. Sciriha, Coalesced and embedded nut graphs in singular graphs, Ars Math. Contemp. 1
(2008), 20–31, doi:10.26493/1855-3974.20.7cc.
[19] I. Sciriha, Graphs with a common eigenvalue deck, Linear Algebra Appl. 430 (2009), 78–85,
doi:10.1016/j.laa.2008.06.033.
[20] I. Sciriha, Maximal core size in singular graphs, Ars Math. Contemp. 2 (2009), 217–229, doi:
10.26493/1855-3974.115.891.
[21] I. Sciriha and P. W. Fowler, Nonbonding orbitals in fullerenes: Nuts and cores in singular
polyhedral graphs, J. Chem. Inf. Model. 47 (2007), 1763–1775, doi:10.1021/ci700097j.
[22] I. Sciriha and I. Gutman, Nut graphs: Maximally extending cores, Util. Math. 54 (1998), 257–
272.
[23] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 9.2), 2020,
http://www.sagemath.org/.
Ac
ce
pt
ed
 m
an
us
cr
ip
t
N. Bašić et al.: On 12-regular nut graphs 9
Appendix A 12-regular nut graphs of odd orders
Here, we list one 12-regular nut graph of odd order n for each n ∈ {17, 19, . . . , 39}.
Each graph is given in the adjacency-lists (of neighbours of each vertex) representation,
formatted as a Python dictionary. We also give the corresponding kernel eigenvector c as a
list of integer entries.
Order n = 17.
{0: [1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 15, 16], 1: [0, 2, 3, 4, 6, 7, 8, 9, 10, 11, 15, 16], 2: [0, 1, 4, 5, 6, 7,
8, 9, 10, 11, 13, 15], 3: [0, 1, 4, 6, 7, 8, 9, 11, 12, 14, 15, 16], 4: [0, 1, 2, 3, 5, 6, 8, 9, 10, 11, 13, 16],
5: [0, 2, 4, 6, 7, 8, 9, 10, 12, 13, 14, 15], 6: [1, 2, 3, 4, 5, 7, 8, 9, 12, 13, 14, 15], 7: [1, 2, 3, 5, 6, 8,
10, 11, 12, 13, 14, 16], 8: [0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 13, 14], 9: [0, 1, 2, 3, 4, 5, 6, 10, 12, 13, 14,
16], 10: [0, 1, 2, 4, 5, 7, 8, 9, 12, 14, 15, 16], 11: [0, 1, 2, 3, 4, 7, 8, 12, 13, 14, 15, 16], 12: [0, 3, 5, 6,
7, 9, 10, 11, 13, 14, 15, 16], 13: [2, 4, 5, 6, 7, 8, 9, 11, 12, 14, 15, 16], 14: [3, 5, 6, 7, 8, 9, 10, 11, 12,
13, 15, 16], 15: [0, 1, 2, 3, 5, 6, 10, 11, 12, 13, 14, 16], 16: [0, 1, 3, 4, 7, 9, 10, 11, 12, 13, 14, 15]}
c = [3, −3, −2, 2, 1, 2, −1, −2, 3, −1, −1, 1, 1, −1, 1, −1, −2]
Order n = 19.
{0: [1, 2, 5, 7, 9, 10, 11, 12, 13, 14, 16, 18], 1: [0, 3, 5, 6, 7, 10, 12, 13, 14, 15, 17, 18], 2: [0, 4, 6, 7,
8, 9, 10, 11, 12, 16, 17, 18], 3: [1, 6, 7, 8, 10, 11, 12, 13, 14, 16, 17, 18], 4: [2, 5, 6, 7, 8, 11, 12, 13,
14, 15, 17, 18], 5: [0, 1, 4, 7, 8, 9, 11, 12, 13, 14, 15, 17], 6: [1, 2, 3, 4, 7, 8, 9, 10, 14, 15, 16, 17], 7:
[0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 15, 16], 8: [2, 3, 4, 5, 6, 7, 9, 11, 14, 15, 17, 18], 9: [0, 2, 5, 6, 7, 8, 10, 11,
12, 13, 16, 17], 10: [0, 1, 2, 3, 6, 9, 11, 12, 13, 14, 16, 18], 11: [0, 2, 3, 4, 5, 7, 8, 9, 10, 16, 17, 18],
12: [0, 1, 2, 3, 4, 5, 9, 10, 13, 14, 15, 16], 13: [0, 1, 3, 4, 5, 9, 10, 12, 14, 15, 16, 17], 14: [0, 1, 3, 4,
5, 6, 8, 10, 12, 13, 15, 18], 15: [1, 4, 5, 6, 7, 8, 12, 13, 14, 16, 17, 18], 16: [0, 2, 3, 6, 7, 9, 10, 11, 12,
13, 15, 18], 17: [1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 15, 18], 18: [0, 1, 2, 3, 4, 8, 10, 11, 14, 15, 16, 17]}
c = [5, 10, 6, −10, −3, −1, 4, −1, −5, 1, 1, −5, −4, −3, −4, 2, −4, 7, 4]
Order n = 21.
{0: [1, 2, 3, 4, 5, 6, 7, 15, 17, 18, 19, 20], 1: [0, 2, 3, 4, 5, 6, 7, 16, 17, 18, 19, 20], 2: [0, 1, 3, 4, 5, 6,
8, 16, 17, 18, 19, 20], 3: [0, 1, 2, 4, 5, 6, 7, 8, 9, 18, 19, 20], 4: [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 19, 20], 5:
[0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 20], 6: [0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12], 7: [0, 1, 3, 4, 5, 6, 8, 9, 10,
11, 12, 13], 8: [2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14], 9: [3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15], 10: [4,
5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16], 11: [5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17], 12: [6, 7, 8, 9, 10,
11, 13, 14, 15, 16, 17, 18], 13: [7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19], 14: [8, 9, 10, 11, 12, 13,
15, 16, 17, 18, 19, 20], 15: [0, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20], 16: [1, 2, 10, 11, 12, 13, 14,
15, 17, 18, 19, 20], 17: [0, 1, 2, 11, 12, 13, 14, 15, 16, 18, 19, 20], 18: [0, 1, 2, 3, 12, 13, 14, 15, 16,
17, 19, 20], 19: [0, 1, 2, 3, 4, 13, 14, 15, 16, 17, 18, 20], 20: [0, 1, 2, 3, 4, 5, 14, 15, 16, 17, 18, 19]}
c = [1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1]
Order n = 23.
{0: [1, 2, 4, 6, 7, 8, 10, 11, 13, 19, 20, 21], 1: [0, 4, 5, 6, 7, 9, 11, 13, 16, 17, 20, 22], 2: [0, 3, 4, 6,
8, 11, 12, 13, 16, 19, 20, 21], 3: [2, 4, 5, 8, 9, 10, 12, 13, 14, 16, 17, 18], 4: [0, 1, 2, 3, 6, 7, 8, 14,
15, 16, 21, 22], 5: [1, 3, 7, 10, 11, 12, 14, 15, 17, 18, 19, 20], 6: [0, 1, 2, 4, 11, 12, 14, 17, 18, 19, 20,
22], 7: [0, 1, 4, 5, 10, 11, 12, 16, 18, 19, 21, 22], 8: [0, 2, 3, 4, 9, 10, 12, 13, 15, 16, 21, 22], 9: [1, 3,
Ac
ce
pt
ed
 m
an
us
cr
ip
t
10 Art Discrete Appl. Math.
8, 10, 11, 13, 14, 15, 18, 19, 21, 22], 10: [0, 3, 5, 7, 8, 9, 11, 13, 17, 18, 19, 21], 11: [0, 1, 2, 5, 6, 7,
9, 10, 13, 14, 15, 20], 12: [2, 3, 5, 6, 7, 8, 13, 14, 17, 19, 20, 22], 13: [0, 1, 2, 3, 8, 9, 10, 11, 12, 14,
15, 19], 14: [3, 4, 5, 6, 9, 11, 12, 13, 15, 16, 17, 20], 15: [4, 5, 8, 9, 11, 13, 14, 17, 18, 20, 21, 22],
16: [1, 2, 3, 4, 7, 8, 14, 17, 18, 20, 21, 22], 17: [1, 3, 5, 6, 10, 12, 14, 15, 16, 19, 20, 21], 18: [3, 5, 6,
7, 9, 10, 15, 16, 19, 20, 21, 22], 19: [0, 2, 5, 6, 7, 9, 10, 12, 13, 17, 18, 22], 20: [0, 1, 2, 5, 6, 11, 12,
14, 15, 16, 17, 18], 21: [0, 2, 4, 7, 8, 9, 10, 15, 16, 17, 18, 22], 22: [1, 4, 6, 7, 8, 9, 12, 15, 16, 18, 19,
21]}
c = [6, −24, −7, 13, 39, 1, 27, 4, −18, −4, 10, 3, −14, −14, 28, 1, −22, −2, 3, 6, −28,
2, −10]
Order n = 25.
{0: [3, 4, 5, 7, 9, 10, 12, 13, 17, 19, 22, 23], 1: [2, 3, 5, 11, 12, 15, 16, 18, 19, 20, 21, 23], 2: [1, 3,
4, 5, 10, 13, 14, 17, 20, 21, 23, 24], 3: [0, 1, 2, 5, 8, 10, 14, 16, 20, 21, 23, 24], 4: [0, 2, 6, 8, 9, 10,
11, 13, 18, 21, 23, 24], 5: [0, 1, 2, 3, 10, 13, 14, 17, 18, 19, 20, 24], 6: [4, 8, 9, 10, 11, 12, 14, 17, 19,
20, 21, 22], 7: [0, 8, 9, 11, 12, 15, 16, 18, 19, 22, 23, 24], 8: [3, 4, 6, 7, 9, 10, 11, 13, 17, 18, 22, 23],
9: [0, 4, 6, 7, 8, 10, 11, 12, 14, 15, 18, 21], 10: [0, 2, 3, 4, 5, 6, 8, 9, 15, 16, 17, 18], 11: [1, 4, 6, 7, 8,
9, 12, 13, 14, 17, 19, 20], 12: [0, 1, 6, 7, 9, 11, 13, 14, 15, 18, 21, 22], 13: [0, 2, 4, 5, 8, 11, 12, 16,
20, 21, 22, 23], 14: [2, 3, 5, 6, 9, 11, 12, 15, 16, 17, 19, 22], 15: [1, 7, 9, 10, 12, 14, 16, 17, 19, 20,
22, 24], 16: [1, 3, 7, 10, 13, 14, 15, 17, 18, 19, 20, 24], 17: [0, 2, 5, 6, 8, 10, 11, 14, 15, 16, 21, 23],
18: [1, 4, 5, 7, 8, 9, 10, 12, 16, 21, 22, 24], 19: [0, 1, 5, 6, 7, 11, 14, 15, 16, 21, 22, 24], 20: [1, 2, 3,
5, 6, 11, 13, 15, 16, 22, 23, 24], 21: [1, 2, 3, 4, 6, 9, 12, 13, 17, 18, 19, 23], 22: [0, 6, 7, 8, 12, 13, 14,
15, 18, 19, 20, 24], 23: [0, 1, 2, 3, 4, 7, 8, 13, 17, 20, 21, 24], 24: [2, 3, 4, 5, 7, 15, 16, 18, 19, 20, 22,
23]}
c = [29, 20, −31, 7, 5, −13, 32, −19, −12, 1, 31, −12, −8, −6, −49, 17, 3, −17, −21,
20, 33, 7, 1, −2, −16]
Order n = 27.
{0: [2, 3, 4, 5, 6, 7, 21, 22, 23, 24, 25, 26], 1: [2, 3, 4, 5, 6, 7, 8, 22, 23, 24, 25, 26], 2: [0, 1, 3, 4, 5,
6, 7, 8, 23, 24, 25, 26], 3: [0, 1, 2, 4, 5, 6, 7, 8, 9, 24, 25, 26], 4: [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 25, 26],
5: [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 26], 6: [0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12], 7: [0, 1, 2, 3, 4, 5, 6, 9,
10, 11, 12, 13], 8: [1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 14], 9: [3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15],
10: [4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16], 11: [5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17], 12: [6, 7, 8,
9, 10, 11, 13, 14, 15, 16, 17, 18], 13: [7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19], 14: [8, 9, 10, 11, 12,
13, 15, 16, 17, 18, 19, 20], 15: [9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21], 16: [10, 11, 12, 13, 14,
15, 17, 18, 19, 20, 21, 22], 17: [11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23], 18: [12, 13, 14, 15, 16,
17, 19, 20, 21, 22, 23, 24], 19: [13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25], 20: [14, 15, 16, 17, 18,
19, 21, 22, 23, 24, 25, 26], 21: [0, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26], 22: [0, 1, 16, 17, 18, 19,
20, 21, 23, 24, 25, 26], 23: [0, 1, 2, 17, 18, 19, 20, 21, 22, 24, 25, 26], 24: [0, 1, 2, 3, 18, 19, 20, 21,
22, 23, 25, 26], 25: [0, 1, 2, 3, 4, 19, 20, 21, 22, 23, 24, 26], 26: [0, 1, 2, 3, 4, 5, 20, 21, 22, 23, 24,
25]}
c = [1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1]
Order n = 29.
{0: [1, 3, 5, 6, 9, 10, 11, 13, 14, 19, 26, 28], 1: [0, 2, 4, 5, 11, 16, 17, 18, 19, 21, 26, 27], 2: [1, 3, 8,
9, 10, 11, 13, 24, 25, 26, 27, 28], 3: [0, 2, 12, 13, 17, 20, 21, 23, 24, 25, 26, 27], 4: [1, 5, 6, 9, 11, 15,
Ac
ce
pt
ed
 m
an
us
cr
ip
t
N. Bašić et al.: On 12-regular nut graphs 11
16, 17, 20, 22, 23, 28], 5: [0, 1, 4, 7, 12, 15, 16, 19, 20, 22, 24, 25], 6: [0, 4, 7, 8, 9, 11, 15, 17, 18,
19, 21, 22], 7: [5, 6, 8, 11, 12, 13, 15, 16, 18, 20, 22, 24], 8: [2, 6, 7, 10, 12, 15, 19, 20, 21, 24, 26,
27], 9: [0, 2, 4, 6, 12, 14, 15, 20, 22, 23, 24, 27], 10: [0, 2, 8, 13, 16, 17, 18, 20, 21, 23, 25, 26], 11:
[0, 1, 2, 4, 6, 7, 12, 16, 17, 19, 20, 23], 12: [3, 5, 7, 8, 9, 11, 14, 15, 18, 19, 21, 25], 13: [0, 2, 3, 7,
10, 14, 15, 21, 23, 25, 27, 28], 14: [0, 9, 12, 13, 15, 18, 22, 23, 24, 26, 27, 28], 15: [4, 5, 6, 7, 8, 9,
12, 13, 14, 18, 22, 27], 16: [1, 4, 5, 7, 10, 11, 18, 20, 21, 25, 27, 28], 17: [1, 3, 4, 6, 10, 11, 18, 19,
22, 24, 27, 28], 18: [1, 6, 7, 10, 12, 14, 15, 16, 17, 19, 23, 24], 19: [0, 1, 5, 6, 8, 11, 12, 17, 18, 23,
26, 27], 20: [3, 4, 5, 7, 8, 9, 10, 11, 16, 25, 26, 28], 21: [1, 3, 6, 8, 10, 12, 13, 16, 22, 23, 25, 26], 22:
[4, 5, 6, 7, 9, 14, 15, 17, 21, 24, 25, 27], 23: [3, 4, 9, 10, 11, 13, 14, 18, 19, 21, 24, 28], 24: [2, 3, 5,
7, 8, 9, 14, 17, 18, 22, 23, 28], 25: [2, 3, 5, 10, 12, 13, 16, 20, 21, 22, 26, 28], 26: [0, 1, 2, 3, 8, 10,
14, 19, 20, 21, 25, 28], 27: [1, 2, 3, 8, 9, 13, 14, 15, 16, 17, 19, 22], 28: [0, 2, 4, 13, 14, 16, 17, 20,
23, 24, 25, 26]}
c = [1, 1, 37, −13, −20, −42, 21, −5, −36, 25, 5, 30, 41, −25, 21, −6, 6, 17, 34, −34,
−14, −13, 7, −51, −16, 39, 5, −21, 6]
Order n = 31.
{0: [5, 10, 12, 13, 17, 18, 21, 22, 24, 26, 27, 29], 1: [3, 6, 7, 8, 10, 14, 17, 20, 23, 25, 27, 30], 2: [4,
7, 9, 10, 18, 21, 22, 23, 24, 25, 27, 28], 3: [1, 4, 5, 11, 13, 16, 17, 18, 19, 24, 25, 29], 4: [2, 3, 5, 11,
12, 13, 18, 21, 25, 26, 28, 29], 5: [0, 3, 4, 6, 7, 9, 11, 14, 17, 25, 27, 29], 6: [1, 5, 8, 9, 11, 13, 18, 20,
22, 26, 29, 30], 7: [1, 2, 5, 9, 10, 12, 20, 24, 25, 26, 27, 30], 8: [1, 6, 9, 14, 15, 17, 18, 20, 21, 22, 23,
30], 9: [2, 5, 6, 7, 8, 12, 14, 15, 19, 24, 27, 28], 10: [0, 1, 2, 7, 12, 13, 15, 18, 19, 21, 24, 28], 11: [3,
4, 5, 6, 12, 15, 17, 20, 22, 23, 29, 30], 12: [0, 4, 7, 9, 10, 11, 14, 16, 18, 21, 27, 30], 13: [0, 3, 4, 6,
10, 16, 20, 23, 24, 25, 26, 27], 14: [1, 5, 8, 9, 12, 15, 17, 18, 19, 20, 22, 23], 15: [8, 9, 10, 11, 14, 17,
19, 20, 21, 27, 28, 30], 16: [3, 12, 13, 18, 19, 21, 22, 23, 24, 26, 28, 29], 17: [0, 1, 3, 5, 8, 11, 14, 15,
20, 22, 23, 29], 18: [0, 2, 3, 4, 6, 8, 10, 12, 14, 16, 24, 25], 19: [3, 9, 10, 14, 15, 16, 20, 21, 22, 23,
26, 28], 20: [1, 6, 7, 8, 11, 13, 14, 15, 17, 19, 24, 25], 21: [0, 2, 4, 8, 10, 12, 15, 16, 19, 25, 27, 29],
22: [0, 2, 6, 8, 11, 14, 16, 17, 19, 23, 28, 30], 23: [1, 2, 8, 11, 13, 14, 16, 17, 19, 22, 26, 28], 24: [0,
2, 3, 7, 9, 10, 13, 16, 18, 20, 28, 30], 25: [1, 2, 3, 4, 5, 7, 13, 18, 20, 21, 26, 29], 26: [0, 4, 6, 7, 13,
16, 19, 23, 25, 27, 29, 30], 27: [0, 1, 2, 5, 7, 9, 12, 13, 15, 21, 26, 30], 28: [2, 4, 9, 10, 15, 16, 19, 22,
23, 24, 29, 30], 29: [0, 3, 4, 5, 6, 11, 16, 17, 21, 25, 26, 28], 30: [1, 6, 7, 8, 11, 12, 15, 22, 24, 26, 27,
28]}
c = [1, 91, −39, 14, 39, 33, 75, −48, −37, 2, 146, −14, −13, 23, 20, 6, −84, −32, 27, 38,
−93, −66, −43, 21, −79, −43, 18, −15, 59, 1, −8]
Order n = 33.
{0: [1, 2, 3, 4, 5, 6, 27, 28, 29, 30, 31, 32], 1: [0, 2, 3, 4, 5, 6, 7, 11, 28, 29, 31, 32], 2: [0, 1, 3, 4, 5,
6, 7, 8, 29, 30, 31, 32], 3: [0, 1, 2, 4, 5, 6, 7, 8, 9, 30, 31, 32], 4: [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 31, 32], 5:
[0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 32], 6: [0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12], 7: [1, 2, 3, 4, 5, 6, 8, 9, 10,
11, 12, 13], 8: [2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14], 9: [3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15], 10:
[4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 30], 11: [1, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 17], 12: [6, 7, 8, 9, 10,
11, 13, 14, 15, 16, 17, 18], 13: [7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19], 14: [8, 9, 10, 11, 12, 13,
15, 16, 17, 18, 19, 20], 15: [9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21], 16: [10, 11, 12, 13, 14, 15,
17, 18, 19, 20, 21, 22], 17: [11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23], 18: [12, 13, 14, 15, 16, 17,
19, 20, 21, 22, 23, 24], 19: [13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25], 20: [14, 15, 16, 17, 18, 19,
21, 22, 23, 24, 25, 26], 21: [15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27], 22: [16, 17, 18, 19, 20, 21,
23, 24, 25, 26, 27, 28], 23: [17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 29], 24: [18, 19, 20, 21, 22, 23,
Ac
ce
pt
ed
 m
an
us
cr
ip
t
12 Art Discrete Appl. Math.
25, 26, 27, 28, 29, 30], 25: [19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31], 26: [20, 21, 22, 23, 24, 25,
27, 28, 29, 30, 31, 32], 27: [0, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 32], 28: [0, 1, 22, 23, 24, 25, 26,
27, 29, 30, 31, 32], 29: [0, 1, 2, 23, 24, 25, 26, 27, 28, 30, 31, 32], 30: [0, 2, 3, 10, 24, 25, 26, 27, 28,
29, 31, 32], 31: [0, 1, 2, 3, 4, 25, 26, 27, 28, 29, 30, 32], 32: [0, 1, 2, 3, 4, 5, 26, 27, 28, 29, 30, 31]}
c = [1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1,
1, −2, 1, 1, −2, 1]
Order n = 35.
{0: [1, 2, 3, 4, 5, 6, 29, 30, 31, 32, 33, 34], 1: [0, 2, 3, 4, 5, 6, 7, 30, 31, 32, 33, 34], 2: [0, 1, 3, 4, 5,
6, 7, 8, 15, 31, 32, 33], 3: [0, 1, 2, 4, 5, 6, 8, 9, 15, 32, 33, 34], 4: [0, 1, 2, 3, 5, 6, 7, 8, 9, 31, 33, 34],
5: [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 34], 6: [0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12], 7: [1, 2, 4, 5, 6, 8, 9, 10,
11, 12, 13, 21], 8: [2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14], 9: [3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15],
10: [5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 25], 11: [5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17], 12: [6, 7, 8,
9, 10, 11, 13, 14, 15, 16, 17, 18], 13: [7, 8, 9, 10, 11, 12, 14, 16, 17, 18, 19, 34], 14: [8, 9, 10, 11, 12,
13, 15, 16, 17, 18, 19, 20], 15: [2, 3, 9, 10, 11, 12, 14, 16, 17, 18, 19, 20], 16: [10, 11, 12, 13, 14, 15,
17, 18, 19, 20, 21, 22], 17: [11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23], 18: [12, 13, 14, 15, 16, 17,
19, 20, 21, 22, 23, 24], 19: [13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25], 20: [14, 15, 16, 17, 18, 19,
21, 22, 23, 24, 25, 26], 21: [7, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27], 22: [16, 17, 18, 19, 20, 21,
23, 24, 25, 26, 27, 28], 23: [17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 29], 24: [18, 19, 20, 21, 22, 23,
25, 26, 27, 28, 29, 30], 25: [10, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30], 26: [20, 21, 22, 23, 24, 25,
27, 28, 29, 30, 31, 32], 27: [21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 32, 33], 28: [22, 23, 24, 25, 26, 27,
29, 30, 31, 32, 33, 34], 29: [0, 23, 24, 25, 26, 27, 28, 30, 31, 32, 33, 34], 30: [0, 1, 24, 25, 26, 27, 28,
29, 31, 32, 33, 34], 31: [0, 1, 2, 4, 26, 27, 28, 29, 30, 32, 33, 34], 32: [0, 1, 2, 3, 26, 27, 28, 29, 30,
31, 33, 34], 33: [0, 1, 2, 3, 4, 27, 28, 29, 30, 31, 32, 34], 34: [0, 1, 3, 4, 5, 13, 28, 29, 30, 31, 32, 33]}
c = [1, −1, −1, −3, 3, 2, −1, −1, 1, 1, −2, 2, −2, −1, 3, −1, −1, 2, −2, −2, 5, −1, −1,
1, −2, −2, 6, −3, −1, 1, −1, 5, −1, −4, 1]
Order n = 37.
{0: [1, 2, 3, 4, 5, 6, 31, 32, 33, 34, 35, 36], 1: [0, 2, 3, 4, 5, 6, 7, 18, 22, 32, 33, 35], 2: [0, 1, 3, 4, 5,
6, 7, 8, 33, 34, 35, 36], 3: [0, 1, 2, 4, 5, 6, 7, 8, 9, 34, 35, 36], 4: [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 35, 36],
5: [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 36], 6: [0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12], 7: [1, 2, 3, 4, 5, 6, 8, 9,
10, 11, 12, 13], 8: [2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14], 9: [3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 15, 32],
10: [4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16], 11: [5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17], 12: [6, 7, 8,
9, 10, 11, 13, 14, 15, 16, 17, 18], 13: [7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 19, 36], 14: [8, 10, 11, 12,
13, 15, 16, 17, 18, 19, 20, 35], 15: [9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21], 16: [10, 11, 12, 13,
14, 15, 17, 18, 19, 20, 21, 22], 17: [11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23], 18: [1, 12, 14, 15,
16, 17, 19, 20, 21, 22, 23, 24], 19: [13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25], 20: [14, 15, 16, 17,
18, 19, 21, 22, 23, 24, 25, 26], 21: [15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27], 22: [1, 16, 17, 18,
19, 20, 21, 23, 24, 26, 27, 28], 23: [17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 29], 24: [18, 19, 20, 21,
22, 23, 25, 26, 27, 28, 29, 30], 25: [19, 20, 21, 23, 24, 26, 27, 28, 29, 30, 31, 34], 26: [20, 21, 22, 23,
24, 25, 27, 28, 29, 30, 31, 32], 27: [21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 32, 33], 28: [22, 23, 24, 25,
26, 27, 29, 30, 31, 32, 33, 34], 29: [23, 24, 25, 26, 27, 28, 30, 31, 32, 33, 34, 35], 30: [24, 25, 26, 27,
28, 29, 31, 32, 33, 34, 35, 36], 31: [0, 25, 26, 27, 28, 29, 30, 32, 33, 34, 35, 36], 32: [0, 1, 9, 26, 27,
28, 29, 30, 31, 33, 34, 36], 33: [0, 1, 2, 27, 28, 29, 30, 31, 32, 34, 35, 36], 34: [0, 2, 3, 25, 28, 29, 30,
31, 32, 33, 35, 36], 35: [0, 1, 2, 3, 4, 14, 29, 30, 31, 33, 34, 36], 36: [0, 2, 3, 4, 5, 13, 30, 31, 32, 33,
34, 35]}
Ac
ce
pt
ed
 m
an
us
cr
ip
t
N. Bašić et al.: On 12-regular nut graphs 13
c = [2, −3, −4, 5, 1, −1, −1, −4, 5, 2, −5, 1, 1, −1, 6, −5, −4, 7, −1, −5, 4, −5, 3, 6,
−5, −5, 8, −3, 1, 1, −4, 3, 4, −7, −1, 3, 1]
Order n = 39.
{0: [1, 2, 3, 4, 5, 6, 15, 33, 34, 36, 37, 38], 1: [0, 2, 3, 4, 5, 6, 7, 34, 35, 36, 37, 38], 2: [0, 1, 3, 4, 5,
6, 7, 8, 35, 36, 37, 38], 3: [0, 1, 2, 4, 5, 6, 7, 8, 9, 36, 37, 38], 4: [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 37, 38],
5: [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 38], 6: [0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12], 7: [1, 2, 3, 4, 5, 6, 8, 9,
10, 11, 12, 13], 8: [2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14], 9: [3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15],
10: [4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16], 11: [5, 6, 7, 8, 9, 10, 12, 13, 14, 16, 17, 35], 12: [6, 7, 8,
9, 10, 11, 13, 14, 15, 16, 17, 18], 13: [7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19], 14: [8, 9, 10, 11, 12,
13, 15, 16, 17, 18, 19, 20], 15: [0, 9, 10, 12, 13, 14, 16, 17, 18, 19, 20, 21], 16: [10, 11, 12, 13, 14,
15, 17, 18, 19, 20, 21, 22], 17: [11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23], 18: [12, 13, 14, 15, 16,
17, 19, 20, 21, 22, 23, 24], 19: [13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25], 20: [14, 15, 16, 17, 18,
19, 21, 22, 23, 24, 25, 26], 21: [15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27], 22: [16, 17, 18, 19, 20,
21, 23, 24, 25, 26, 27, 28], 23: [17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 29], 24: [18, 19, 20, 21, 22,
23, 25, 26, 27, 28, 29, 30], 25: [19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31], 26: [20, 21, 22, 23, 24,
25, 27, 28, 29, 30, 31, 32], 27: [21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 32, 33], 28: [22, 23, 24, 25, 26,
27, 29, 30, 31, 32, 33, 34], 29: [23, 24, 25, 26, 27, 28, 30, 31, 32, 33, 34, 35], 30: [24, 25, 26, 27, 28,
29, 31, 32, 33, 34, 35, 36], 31: [25, 26, 27, 28, 29, 30, 32, 33, 34, 35, 36, 37], 32: [26, 27, 28, 29, 30,
31, 33, 34, 35, 36, 37, 38], 33: [0, 27, 28, 29, 30, 31, 32, 34, 35, 36, 37, 38], 34: [0, 1, 28, 29, 30, 31,
32, 33, 35, 36, 37, 38], 35: [1, 2, 11, 29, 30, 31, 32, 33, 34, 36, 37, 38], 36: [0, 1, 2, 3, 30, 31, 32, 33,
34, 35, 37, 38], 37: [0, 1, 2, 3, 4, 31, 32, 33, 34, 35, 36, 38], 38: [0, 1, 2, 3, 4, 5, 32, 33, 34, 35, 36,
37]}
c = [1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1,
1, −2, 1, 1, −2, 1, 1, −2, 1, 1, −2, 1]