REVIEW 3 major objections 5 minor 1 cited by
On cubic polycirculant nut graphs
T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read This paper proves that cubic, 3-regular nut graphs with a cyclic symmetry having ℓ equal-sized vertex orbits exist for ℓ=3, 6, 7 and every ℓ≥9, and do not exist for ℓ=1, 2, 4, or 5, leaving ℓ=8 as the only open case.
desk verdict A clean extension of the cubic polycirculant nut graph classification; the positive constructions are solid, but the ℓ=4,5 nonexistence rests on an unpinned Sage script and should be strengthened before publication. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the cyclic voltage pregraph: a pregraph whose darts carry labels in a cyclic group, so that its derived graph is automatically $\ell$-circulant with all orbits of equal size. The null space of the derived graph is controlled by orbit magnitudes, the common absolute value of a kernel vector on each orbit. Proposition 7 turns possible nutness into a finite linear algebra test: a quotient pregraph can yield a nut graph only if some sign matrix $B$ with $|B|=A(X)$ has a positive null vector, which is checked by integer linear programming. On the construction side, Lemmas 9 and 12 reduce the nut condition for the built families to a cyclotomic-polynomial criterion: an explicit polynomial must have only $-1$ as a root among the $n$-th roots of unity. The pre-subdivision construction then inserts three new vertices into any edge whose endpoint orbits have different magnitudes, raising $\ell$ by 3 while keeping the kernel one-dimensional and full.
What would settle it
Exhibit one cubic 4- or 5-circulant nut graph, or independently re-run the authors' enumeration and find a quotient pregraph it omits or a positive-kernel sign matrix it rejects; either would break Theorem 8 and hence the negative half of Theorem 2.
Extended reading notes
Core claim
The central claim, Theorem 2, is a dichotomy for cubic $\ell$-circulant nut graphs: $\ell\in\{1,2,4,5\}$ is impossible, while $\ell=3,6,7$ or $\ell\ge 9$ yields infinitely many examples. The paper models every cubic $\ell$-circulant graph as the derived graph of a cyclic voltage pregraph on $\ell$ vertices. For $\ell=4$ and $\ell=5$, it enumerates all connected cubic quotient pregraphs (12 and 22 of them, respectively) and uses an orbit-magnitude argument to show none can give a nut graph. For the positive half, it constructs explicit voltage pregraphs producing infinite families of 7- and 11-circulant nut graphs, then proves a pre-subdivision lemma: replacing an edge whose endpoint orbits have different magnitudes by a three-vertex path raises $\ell$ by 3 and preserves the nut property. Iterating this lemma from the $\ell=3$, $\ell=7$, and $\ell=11$ families covers every $\ell\ge 9$, leaving $\ell=8$ as the sole open case, which the authors conjecture to be empty.
Load-bearing premise
The nonexistence for 4 and 5 orbits hangs on the authors' computer program being exhaustive and correct; the paper gives no independent certificate that the search missed nothing.
Editorial extensions
If this is right
- Every $\ell$ except 8 is now decided: 1, 2, 4, and 5 are impossible, and 3, 6, 7, and all $\ell\ge 9$ have infinitely many cubic nut graphs.
- The pre-subdivision lemma can be applied repeatedly, so from any eligible seed there are infinite families at $\ell$, $\ell+3$, $\ell+6$, ...; this covers the progressions 3, 6, 9, ..., 7, 10, 13, ..., and 11, 14, 17, ....
- The nonexistence for $\ell=4$ and $\ell=5$ is a finite computation: all connected cubic quotient pregraphs of order 4 and 5 (12 and 22 of them) are inspected, and none can carry a positive kernel vector.
- The constructions give concrete orders: a 7-orbit nut graph of order $7n$ for every even $n\ge 4$, and an 11-orbit nut graph of order $11n$ for every $n\ge 6$ with $n\equiv 2 \pmod 4$.
- The only remaining orbit count is $\ell=8$; Conjecture 16 states that no cubic 8-circulant nut graph exists.
Reading between the lines
- Because the paper tabulates 534 quotient pregraphs for $\ell=8$, the same enumeration pipeline is immediately applicable to test the open case; making the computer search independently verifiable would turn the $\ell=4$ and $\ell=5$ result into a checkable proof.
- The pre-subdivision construction only needs two adjacent orbits of different magnitudes, so the same mechanism could generate infinite orbit-count families in higher-degree regular nut graphs, though the paper stays with the cubic case.
- The cyclotomic-polynomial criterion behind Lemmas 9 and 12 looks like a general recipe: build a voltage pregraph whose null space reduces to a circulant matrix, then prove the corresponding polynomial has only $-1$ as a root of unity. That recipe may help attack the open degree-order-orbit problem stated as Problem 17.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies cubic ℓ-circulant nut graphs, i.e., cubic nut graphs admitting a cyclic automorphism group with ℓ equal-sized vertex orbits. Its main theorem states that cubic ℓ-circulant nut graphs do not exist for ℓ = 1, 2, 4, 5 and exist in infinitely many instances for every ℓ in {3, 6, 7} or ℓ ≥ 9, leaving only ℓ = 8 open. The proof combines a computer-assisted search over cubic quotient pregraphs of order 4 and 5 (Sections 2–3), explicit voltage-graph constructions for cubic 7- and 11-circulant nut graphs with cyclotomic polynomial criteria (Sections 4–5), and a "pre-subdivision" operation that increases the number of orbits by three and is iterated to cover the remaining congruence classes (Section 6). The case ℓ = 3 is imported from the authors' earlier classification of cubic tricirculant nut graphs [12].
Significance. If the main theorem is correct, the paper resolves the cubic polycirculant nut-graph existence question for every orbit count except ℓ = 8, a substantial advance over the previously known cubic 1-, 2-, and 3-circulant cases. The positive constructions are explicit and checkable by hand: each family is verified through elementary reductions to root-of-unity conditions, and the cyclotomic divisibility arguments are sound. The pre-subdivision construction is a simple and potentially reusable mechanism for increasing the orbit count. The principal weakness is that the negative results for ℓ = 4, 5 are not backed by machine-checkable certificates in the manuscript, and several assertions about the magnitude condition required for iteration are not proved here. With those gaps closed, the paper would be a strong contribution.
major comments (3)
- [Section 3, Theorem 8] The nonexistence of cubic 4- and 5-circulant nut graphs is established only by the statement that running the SageMath script from [1] yields this result. The manuscript provides the counts Q(4) = 12 and Q(5) = 22 and a description of the two-step test (Propositions 6 and 7), but it does not include the code, a commit hash, an output log, or machine-checkable certificates for the per-pregraph ILP checks. Since Theorem 8 is the entire support for the negative half of Theorem 2 for ℓ = 4, 5, this is a load-bearing verification gap; please provide reproducible scripts with versioned repository contents, full output logs, certificates, or an independent verification of the enumeration and of the absence of positive null vectors.
- [Proof of Theorem 2, final paragraph] The claim that all Zn-voltage pregraphs of order three from [12, Theorems 2, 11 and 14] satisfy the hypothesis of Lemma 15 (two adjacent orbits of different magnitudes) is asserted without proof or a precise quotation. This condition is needed to obtain infinitely many cubic ℓ-circulant nut graphs for ℓ = 3, 6, 9, 12, ...; please supply a short argument or exact references to the statements in [12] that imply it.
- [Section 6, paragraph after Lemma 15] The preservation of the different-magnitude condition under the pre-subdivision construction is asserted without proof: the text states that if the starting pregraph satisfies the condition, then so does the constructed pregraph. Since the construction is iterated to obtain ℓ = 10, 13, ... and ℓ = 14, 17, ..., this claim is load-bearing; please add the short magnitude computation or state explicitly which adjacent pair in the constructed pregraph has different magnitudes.
minor comments (5)
- [Proposition 10, first case] In the second paragraph of the proof, the polynomial should be 2x^2 - x + 2, not 2x^2 + x + 2, matching the factorization (x + 1)^2 (2x^2 - x + 2).
- [Proof of Theorem 2] The phrase 'Theorem 1 and Proposition 8' should read 'Theorem 1 and Theorem 8', since Proposition 8 is not stated in the paper.
- [Lemma 12] The notation '2 | α, β' is ambiguous; it should be written as '2 divides α and β' or 'α and β are even'.
- [Reference [1]] The GitHub repository link should include a commit hash or version identifier so that the computational results are reproducible.
- [Proof of Proposition 7] The sentence 'It is obvious that the vertices y1, y2, y3 cannot all reside in the same orbit' could benefit from a one-sentence justification, since the argument is short but not completely immediate.
Circularity Check
No significant circularity: the paper's constructions and nonexistence arguments are explicit and checkable, and its self-citations are background results rather than load-bearing circular inputs.
full rationale
The paper's derivation chain is self-contained in the relevant sense. The positive cases reduce, via exact linear algebra, to root conditions on explicit cyclotomic polynomials: Lemma 9 and Lemma 12 translate the nut-graph condition into a polynomial containing only -1 as a root among n-th roots of unity, and Propositions 10 and 13 verify those conditions by explicit factorizations such as (x-1)^2(2x^2+x+2). Lemma 15 gives an explicit pre-subdivision construction whose proof is a direct local-condition argument. The negative cases for ell=4,5 rest on a finite computer search using Propositions 6 and 7, which are derived rather than assumed; the search enumerates finitely many pregraphs and sign matrices, so no parameter is fitted from the target nonexistence claim. The self-citations, chiefly [12] for the cubic 3-circulant classification and ℓ=2 nonexistence and [10] for the circulant order-degree theorem, are published external results used as inputs, not as devices that make the conclusion equivalent to the premise. The reliance on an unpinned SageMath repository [1] for the computational nonexistence of cubic 4- and 5-circulant nut graphs is a reproducibility and verification concern, not a circularity concern: nothing in the paper defines the target result in terms of the script's output, and the script's role is an independent finite computation rather than a parameter fitted to the conclusion.
Assumptions & free parameters
assumptions (5)
- standard math Cyclotomic polynomials are irreducible over Q[x], so a polynomial contains a primitive b-th root of unity iff it is divisible by Φ_b(x).
- standard math The spectrum of a circulant matrix of order n is given by evaluating its first row polynomial at n-th roots of unity.
- standard math The local condition for membership in the null space, and the basic properties of nut graphs: connected, nonbipartite, leafless, and fixed orbit sign behavior.
- domain assumption Every cubic ℓ-circulant graph of order n is the derived graph of a cubic Z_{n/ℓ}-voltage pregraph on ℓ vertices.
- domain assumption In a cubic quotient pregraph with ℓ ≥ 3, each vertex has at most one semi-edge and no triple edges occur.
Cite this review
Pith. "Pith review of On cubic polycirculant nut graphs." pith.science (2026). https://pith.science/paper/SCWBUHPE
@misc{pith2026241116904,
author = {Pith},
title = {Pith review of: On cubic polycirculant nut graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/SCWBUHPE}},
note = {Machine review of arXiv:2411.16904}
}
abstract
A nut graph is a nontrivial simple graph whose adjacency matrix contains a one-dimensional null space spanned by a vector without zero entries. Moreover, an $\ell$-circulant graph is a graph that admits a cyclic group of automorphisms having $\ell$ vertex orbits of equal size. It is not difficult to observe that there exists no cubic $1$-circulant nut graph or cubic $2$-circulant nut graph, while the full classification of all the cubic $3$-circulant nut graphs was recently obtained [Electron. J. Comb. 31(2) (2024), #2.31]. Here, we investigate the existence of cubic $\ell$-circulant nut graphs for $\ell \ge 4$ and show that there is no cubic $4$-circulant nut graph or cubic $5$-circulant nut graph by using a computer-assisted proof. Furthermore, we rely on a construction based approach in order to demonstrate that there exist infinitely many cubic $\ell$-circulant nut graphs for any fixed $\ell \in \{6, 7 \}$ or $\ell \ge 9$.
Figures
Figures from the paper (1 more)
Forward citations
Cited by 1 Pith paper
-
Classification of quartic bicirculant nut graphs
Quartic bicirculant nut graphs are exactly the B1, B2 and B3 parameter families described in Theorem 1.1 with the stated gcd, parity and congruence conditions; no B4 graph is a nut graph.
Reference graph
Works this paper leans on
-
[12]
I. Damnjanovi´ c, N. Baˇ si´ c, T. Pisanski and A.ˇZitnik, Classification of cubic tricirculant nut graphs, Electron. J. Comb. 31(2) (2024), #2.31, https:// doi.org/10.37236/12668. 20
-
[1]
N. Baˇ si´ c and I. Damnjanovi´ c, On cubic polycirculant nut graphs: supplemen- tary material (GitHub repository), https://github.com/nbasic/cubic- polycirculant-nuts
-
[2]
N. Baˇ si´ c and P. W. Fowler, Nut graphs with a given automorphis m group, 2024, arXiv:2405.04117 [math.CO]
arXiv 2024
-
[3]
N. Baˇ si´ c, P. W. Fowler and T. Pisanski, Vertex and edge orbits in nut graphs, Electron. J. Comb. 31(2) (2024), #P2.38, https://doi.org/10. 37236/12619
work page 2024
-
[4]
N. Baˇ si´ c, M. Knor and R.ˇSkrekovski, On 12-regular nut graphs, Art Discrete Appl. Math. 5(2) (2022), #P2.01, https://doi.org/10.26493/2590-9770. 1403.1b1
-
[5]
G. Brinkmann, N. Van Cleemput and T. Pisanski, Generation of var ious classes of trivalent graphs, Theor. Comput. Sci. 502 (2013), 16–29, https:// doi.org/10.1016/j.tcs.2012.01.018
-
[6]
K. Coolsaet, P. W. Fowler and J. Goedgebeur, Generation and pr oper- ties of nut graphs, MATCH Commun. Math. Comput. Chem. 80 (2018), 423–444, https://match.pmf.kg.ac.rs/electronic_versions/Match80/ n2/match80n2_423-444.pdf
work page 2018
-
[7]
D. Cvetkovi´ c, M. Doob and H. Sachs, Spectra of graphs: Theory and applica- tions, Leipzig: J. A. Barth Verlag, 1995
work page 1995
Show all 39 references
-
[8]
Damnjanovi´ c, A note on Cayley nut graphs whose degree is d ivisible by four, 2023, arXiv:2305.18658 [math.CO]
I. Damnjanovi´ c, A note on Cayley nut graphs whose degree is d ivisible by four, 2023, arXiv:2305.18658 [math.CO]
2023 arXiv
-
[9]
Damnjanovi´ c, Two families of circulant nut graphs, Filomat 37(24) (2023), 8331–8360, https://doi.org/10.2298/FIL2324331D
I. Damnjanovi´ c, Two families of circulant nut graphs, Filomat 37(24) (2023), 8331–8360, https://doi.org/10.2298/FIL2324331D
2023 doi
-
[10]
Damnjanovi´ c, Complete resolution of the circulant nut gra ph order–degree existence problem, Ars Math
I. Damnjanovi´ c, Complete resolution of the circulant nut gra ph order–degree existence problem, Ars Math. Contemp. 24(4) (2024), #P4.03, https:// doi.org/10.26493/1855-3974.3009.6df
2024
-
[11]
Damnjanovi´ c, On the null spaces of quartic circulant graphs, Discrete Math
I. Damnjanovi´ c, On the null spaces of quartic circulant graphs, Discrete Math. Chem. (2024), in press
2024
-
[13]
Damnjanovi´ c and D
I. Damnjanovi´ c and D. Stevanovi´ c, On circulant nut graph s, Linear Alge- bra Appl. 633 (2022), 127–151, https://doi.org/10.1016/j.laa.2021.10. 006
2022 doi
-
[14]
P. W. Fowler, J. B. Gauci, J. Goedgebeur, T. Pisanski and I. Sc iriha, Existence of regular nut graphs for degree at most 11, Discuss. Math. Graph Theory 40 (2020), 533–557, https://doi.org/10.7151/dmgt.2283
2020 doi
-
[15]
P. W. Fowler, B. T. Pickup, T. Z. Todorova, M. Borg and I. Scirih a, Omni- conducting and omni-insulating molecules, J. Chem. Phys. 140(5) (2014), 054115, https://doi.org/10.1063/1.4863559
2014 doi
-
[16]
P. W. Fowler, T. Pisanski and N. Baˇ si´ c, Charting the space o f chemi- cal nut graphs, MATCH Commun. Math. Comput. Chem. 86(3) (2021), 519–538, https://match.pmf.kg.ac.rs/electronic_versions/Match86/ n3/match86n3_519-538.pdf
2021
-
[17]
J. B. Gauci, T. Pisanski and I. Sciriha, Existence of regular nut graphs and the Fowler construction, Appl. Anal. Discrete Math. 17(2) (2023), 321–333, https://doi.org/10.2298/AADM190517028G
2023 doi
-
[18]
R. M. Gray, Toeplitz and circulant matrices: a review, Found. Trends Com- mun. Inf. Theory 2 (2006), 155–239, https://ee.stanford.edu/~gray/ CIT006-journal.pdf
2006
-
[19]
G. J. O. Jameson, The cyclotomic polynomials, https://www.maths.lancs. ac.uk/~jameson/cyp.pdf
-
[20]
Malniˇ c, D
A. Malniˇ c, D. Maruˇ siˇ c and P. Potoˇ cnik, Elementary Abeliancovers of graphs, J. Algebraic Combin. 20 (2004), 71–97, https://doi.org/10.1023/B:JACO. 0000047294.42633.25
2004
-
[21]
Malniˇ c, R
A. Malniˇ c, R. Nedela and M. ˇSkoviera, Lifting graph automorphisms by volt- age assignments, European J. Combin. 21 (2000), 927–947, https://doi. org/10.1006/eujc.2000.0390
2000
-
[22]
B. D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symb. Com- put. 60 (2014), 94–112, https://doi.org/10.1016/j.jsc.2013.09.003
2014 doi
-
[23]
Pisanski, A classification of cubic bicirculants, Discrete Math
T. Pisanski, A classification of cubic bicirculants, Discrete Math. 307(3–5) (2007), 567–578, https://doi.org/10.1016/j.disc.2005.09.053
2007 doi
-
[24]
Pisanski and B
T. Pisanski and B. Servatius, Configurations from a graphical viewpoint , Springer, New York, Birkh¨ auser Advanced Texts Basler Lehrb¨ ucher, 2013, https://doi.org/10.1007/978-0-8176-8364-1 . 21
2013 doi
-
[25]
Potoˇ cnik and M
P. Potoˇ cnik and M. Toledo, Classification of cubic vertex-tran sitive tricircu- lants, Ars. Math. Contemp. 18 (2020), 1–31, https://doi.org/10.26493/ 1855-3974.1815.b52
2020
-
[26]
Sciriha, On the coefficient of λ in the characteristic polynomial of singular graphs, Util
I. Sciriha, On the coefficient of λ in the characteristic polynomial of singular graphs, Util. Math. 52 (1997), 97–111
1997
-
[27]
Sciriha, On singular line graphs of trees, Congr
I. Sciriha, On singular line graphs of trees, Congr. Numerantium 135 (1998), 73–91
1998
-
[28]
Sciriha, On the construction of graphs of nullity one, Discrete Math
I. Sciriha, On the construction of graphs of nullity one, Discrete Math. 181(1–
-
[29]
(1998), 193–211, https://doi.org/10.1016/S0012-365X(97)00036-8
1998 doi
-
[30]
Sciriha, The two classes of singular line graphs of trees, Rend
I. Sciriha, The two classes of singular line graphs of trees, Rend. Semin. Mat. Messina, Ser. II 20(5) (1999), 167–180
1999
-
[31]
Sciriha, A characterization of singular graphs, Electron
I. Sciriha, A characterization of singular graphs, Electron. J. Linear Algebra , 16 (2007), 451–462, https://eudml.org/doc/129125
2007
-
[32]
Sciriha, Coalesced and embedded nut graphs in singular graph s, Ars Math
I. Sciriha, Coalesced and embedded nut graphs in singular graph s, Ars Math. Contemp. 1 (2008), 20–31, https://doi.org/10.26493/1855-3974.20.7cc
2008 doi
-
[33]
Sciriha and A
I. Sciriha and A. Farrugia, From nut graphs to molecular structure and con- ductivity, University of Kragujevac, Kragujevac, volume 23 of Mathematical chemistry monographs, 2021
2021
-
[34]
Sciriha and P
I. Sciriha and P. W. Fowler, Nonbonding orbitals in fullerenes: nut s and cores in singular polyhedral graphs, J. Chem. Inf. Model. 47(5) (2007), 1763–1775, https://doi.org/10.1021/ci700097j
2007 doi
-
[35]
Sciriha and P
I. Sciriha and P. W. Fowler, On nut and core singular fullerenes, Dis- crete Math. 308(2–3) (2008), 267–276, https://doi.org/10.1016/j.disc. 2006.11.040
2008 doi
-
[36]
Sciriha and I
I. Sciriha and I. Gutman, Nut graphs: maximally extending cores , Util. Math. 54 (1998), 257–272
1998
-
[37]
Van Cleemput, Sequence A243391, in: The On-Line Encyclopedia of Integer Sequences, 2014, https://oeis.org/A243391
N. Van Cleemput, Sequence A243391, in: The On-Line Encyclopedia of Integer Sequences, 2014, https://oeis.org/A243391
2014
-
[38]
Van Cleemput, Sequence A243393, in: The On-Line Encyclopedia of Integer Sequences, 2014, https://oeis.org/A243393
N. Van Cleemput, Sequence A243393, in: The On-Line Encyclopedia of Integer Sequences, 2014, https://oeis.org/A243393
2014
-
[39]
The Sage Developers, SageMath, the Sage Mathematics Softw are System (Version 9.5), 2022, https://www.sagemath.org. 22
2022
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.