REVIEW 2 major objections 4 minor 33 references
Classification of quartic bicirculant nut graphs
T0 review · 2 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read A quartic bicirculant graph is a nut graph exactly when it is one of three explicitly described families, and no graph from the fourth family is a nut graph.
desk verdict Solid classification with a real but repairable verification gap in the B1 branch. 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 machinery is the eigenvalue formula for bicirculants as $\mathbb{Z}_m$-covers: the eigenvalues are $\frac{\lambda^S_k+\lambda^T_k \pm \sqrt{(\lambda^S_k-\lambda^T_k)^2+4|\lambda^R_k|^2}}{2}$, where $\lambda^S_k,\lambda^T_k,\lambda^R_k$ are sums of roots of unity coming from the parameter sets $S,T,R$. From this, zero is an eigenvalue with multiplicity one exactly when $|\lambda^R_k|^2=\lambda^S_k\lambda^T_k$ for exactly one $k$. Substituting the parameters and clearing denominators turns this into a non-divisibility statement for explicit lacunary polynomials ($R_{a,b}$, $Q_{a,b}$, $P_{a,b,c}$, or $(x^{b-a}+1)(x^a+1)(x^b+1)$) by cyclotomic polynomials $\Phi_f$. Two tools finish the job: a theorem on divisibility of lacunary polynomials by cyclotomic polynomials, which strips large prime factors from $f$, and a case analysis reducing the remaining divisors to short finite lists, so the whole classification ends in a handful of modular checks.
What would settle it
Run an exhaustive search over all connected quartic bicirculants of order $n$ from 52 up to, say, 200, computing the nullity of the adjacency matrix and checking whether a kernel vector has zero entries. Any graph outside the three families of the main theorem with nullity one and a zero-free kernel vector, or any listed graph whose parameters satisfy the conditions but whose nullity is not one, would refute the classification; the paper's own tables only certify orders up to 50.
Extended reading notes
Core claim
On the paper's own terms, the central claim is a complete if-and-only-if description. A connected quartic bicirculant graph is a nut graph exactly when, up to isomorphism, it is $B1(m;a,b)$ with $m\equiv_4 2$, $a$ and $b$ even, $\gcd(m/2,a,b)=1$, and (if $5\mid m$) one of $a,b,a-b,a+b$ divisible by $5$; or $B2(m;a,b,c)$ with the four conditions of its classification theorem: coprimality of four gcd expressions, a 2-adic valuation inequality, and forbidden residue triples modulo $12$ and $30$; or $B3(m;a,b)$ with $a,b$ odd, $\gcd(m,a)=\gcd(m,b)=1$, and $v_2(b-a)\ge v_2(m)$. The fourth class, $B4$, contains no nut graphs because its members are bipartite cyclic Haar graphs.
Load-bearing premise
The load-bearing premise is that the finite cyclotomic-divisibility tables used in the B1 branch—cited from the authors' earlier paper and not reproduced here—are correct and exhaustive, so that no missing divisor $f$ escapes the reduction.
Editorial extensions
If this is right
- If the theorem holds, the nut-graph question for quartic bicirculants is decidable by arithmetic: checking a graph means checking finitely many gcd and congruence conditions, never computing a spectrum.
- Since every $B4$ graph is bipartite and bipartite graphs are never nut graphs, the family of quartic bicirculant nut graphs is exactly the union of the nut graphs in $B1$, $B2$, and $B3$.
- The Rose Window graphs, obtained by setting $a=1$ in $B2$, receive a complete nut-graph classification as a special case.
- For prime $m$, the classification implies that among connected quartic bicirculants of class $B2$ there is exactly one non-nut graph up to isomorphism, namely $B2(m;1,1,2)$.
- The $B1$ remark ties the classification to $I$-graphs: $B1(m;a,b)$ is the product $I(m/2,a/2,b/2)\square K_2$, so the $B1$ nut graphs correspond exactly to $I$-graphs having $1$ or $-1$ as a simple eigenvalue.
Reading between the lines
- The same spectrum-plus-cyclotomic reduction should apply to classify nut graphs among other two-orbit families of fixed degree; the hard part is only carrying the finite divisibility checks through.
- The arithmetic conditions yield a fast recognition algorithm, so the enumeration table, which currently certifies only orders up to 50, could be extended to much larger orders, and the open question of graphs belonging to more than one of the classes could be tested computationally.
- Because $B2$ gives nut graphs for almost all admissible parameter triples when $m$ is prime, the classification suggests a density analysis of quartic bicirculant nut graphs by order, a count not attempted in the paper.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper classifies connected quartic bicirculant graphs that are nut graphs. Using the four classes B1-B4 of connected quartic bicirculants, it proves Theorem 1.1: B1(m;a,b) is a nut graph exactly under conditions 1(i)-(iv), B2(m;a,b,c) under conditions 2(i)-(iv), B3(m;a,b) under the stated parity, coprimality and 2-adic conditions, and no B4 graph is a nut graph. The proof reduces the nut-graph condition to a simple zero eigenvalue (Lemma 2.4), applies the known spectral formula for bicirculants (Theorem 2.5), and translates the zero-eigenvalue condition into divisibility of eight-term lacunary polynomials by cyclotomic polynomials, which is then analyzed with the Filaseta-Schinzel theorem and finite residue checks.
Significance. The classification is a natural completion of the programme that classified quartic circulant nut graphs and cubic tricirculant nut graphs; if the B1 branch is verified, it gives a complete parametric description of quartic bicirculant nut graphs. The B2 branch is backed by a reproducible SageMath script in Appendix A, and the B3 branch has a short elementary proof; the spectral reduction to cyclotomic divisibility is clean and yields explicit forbidden congruence conditions. The main weakness is that the B1 sufficiency depends on a finite computation cited from the authors' earlier paper [13] and not reproduced here, so the completeness of the B1 branch is currently a verification statement rather than a demonstrated computation.
major comments (2)
- [Section 3, proof of Theorem 3.1 (final paragraph)] The 'if' direction of Theorem 3.1 rests on the sentence 'As indicated by the computational results given in [13, Sections A and B]...' after Lemma 3.6 has reduced the problem to showing that Phi_f does not divide R_mod for f in {3,5,7,15,21} and Phi_f does not divide Q_mod for f in {6,10,14,30,42} under conditions (i)-(iv). These finite non-divisibility checks are load-bearing: without them Lemma 3.6 only gives a reduction, not a classification. Neither the tables nor the code for these checks appear in this manuscript, and [13] is a different classification (cubic tricirculant nut graphs), so a reader cannot verify that the residue computations were performed for exactly the polynomials (2) and (3) with the hypotheses 1(i)-(iv). I recommend either reproducing the finite checks (e.g., a script analogous to Appendix A together with the resulting tables) or stating precisely which lemmas of [13] imply these non-divisibilities.
- [Section 4, Lemma 4.5, Case 1] In the proof of Lemma 4.5, Case 1, the claim '4 does not divide c cannot be true, since otherwise condition (i) would not hold' is false: for m=16, a=b=4, c=1, conditions (i) and (ii) of Theorem 4.1 hold and 4 does not divide c. The intended conclusion that a+b has a unique remainder modulo 8 remains true in the odd-c subcase because a+b+2c and a+b are the only even terms and are distinct modulo 8, but the proof as written does not cover that subcase. This proof step is used in the reduction of the B2 classification, so it should be corrected.
minor comments (4)
- [Lemma 3.2 and Lemma 5.2] The complex conjugate of zeta is rendered as 'zeta != zeta' in the proofs of Lemma 3.2 and Lemma 5.2; it should be zeta-bar, the complex conjugate.
- [Section 5, Theorem 5.1 and its proof] The sentence 'with even n >= 4' and the condition '1 <= a < b < n' use the symbol n where the parameter m is meant; these should be m to match the rest of the paper.
- [Appendix A, SageMath script] In the script, condition (ii) is coded using v2(f) rather than v2(m). Since f divides m, this filters fewer triples than the theorem's condition, so the script actually verifies a stronger statement; the proof of Theorem 4.1 says 'provided conditions (i) and (ii) hold' without commenting on this difference, which may confuse readers trying to reproduce the check.
- [Section 6, Table 1] The enumeration counts Cn, Bn, Nn, Vn, Yn, Zn in Table 1 are presented without a description of the enumeration procedure; a short paragraph on how the counts were obtained and whether the classification theorem was used would make the table reproducible.
Circularity Check
No significant circularity: the classification is derived from eigenvalue and cyclotomic reductions; the only weak point is the B1 branch's reliance on the same authors' earlier computational tables [13], a reproducibility gap rather than a circular step.
full rationale
The derivation chain is not circular. Theorem 2.5 gives the bicirculant eigenvalues, Lemma 2.4 upgrades a simple zero eigenvalue to a nut eigenvector for B1-B3, and each class is then reduced to non-divisibility of an explicit lacunary polynomial by cyclotomic polynomials. For class B2 the final finite verification is executed by the SageMath script printed in Appendix A, and the congruence conditions in Theorem 4.1 are read off from that run. For class B3 the proof is a self-contained reduction to the linear congruence k*ell = m/2 mod m. The only externally imported, load-bearing material is in Section 3: the proofs of Lemmas 3.4 and 3.5 and the final finite cyclotomic check for B1 depend on [13], the authors' earlier published classification of cubic tricirculant nut graphs, and those tables are not reproduced here. This is a verification/reproducibility gap, not a circular reduction: [13] addresses a different graph family, its lemmas concern the same two 8-term polynomials but do not presuppose the quartic bicirculant classification, and no fitted parameter or definition-in-terms-of-the-conclusion is involved. Because the cited results are external, published, and falsifiable by independent computation, the self-citation does not force the main theorem. Score 2 reflects the minor self-citation dependency, not circularity.
Assumptions & free parameters
assumptions (7)
- standard math Cyclotomic polynomials Phi_f are irreducible over Q
- domain assumption Theorem 2.5 spectral formula for BiCirc(m;S,T,R)
- standard math Lemma 2.3: a simple eigenvector is constant or alternating on automorphism orbits
- standard math Filaseta-Schinzel theorem on lacunary polynomials divisible by cyclotomic polynomials
- domain assumption Four-class decomposition of connected quartic bicirculants
- domain assumption B3(m;a,b) isomorphism normalization: isomorphic to B3(m;-a,b-a) and B3(m;-b,a-b)
- domain assumption Correctness of the B1 finite computational checks in [13, Sections A and B]
Cite this review
Pith. "Pith review of Classification of quartic bicirculant nut graphs." pith.science (2026). https://pith.science/paper/FX7CWTZW
@misc{pith2026250206353,
author = {Pith},
title = {Pith review of: Classification of quartic bicirculant nut graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/FX7CWTZW}},
note = {Machine review of arXiv:2502.06353}
}
read the original abstract
A graph is called a nut graph if zero is its eigenvalue of multiplicity one and its corresponding eigenvector has no zero entries. A graph is a bicirculant if it admits an automorphism with two equally sized vertex orbits. There are four classes of connected quartic bicirculant graphs. We classify the quartic bicirculant graphs that are nut graphs by investigating properties of each of these four classes.
Figures
Reference graph
Works this paper leans on
-
[13]
I. Damnjanovi´ c, N. Baˇ si´ c, T. Pisanski and A.ˇZitnik, Classification of cubic tricirculant nut graphs, Electron. J. Comb. 31 (2024), #P2.01
work page 2024
-
[1]
On cubic polycirculant nut graphs
N. Baˇ si´ c and I. Damnjanovi´ c, On cubic polycirculant nut gra phs, arXiv:2411.16904 [math.CO], 2024
work page Pith review arXiv 2024
-
[2]
On the degrees of regular nut graphs and Cayley nut graphs
N. Baˇ si´ c, I. Damnjanovi´ c and P. W. Fowler, On the degrees of regular nut graphs, arXiv:2410.14063 [math.CO], 2024. 17
work page Pith review arXiv 2024
-
[3]
Nut graphs with a given automorphism group
N. Baˇ si´ c and P. W. Fowler, Nut graphs with a given automorphis m group, arXiv:2405.04117 [math.CO], 2024
work page Pith review arXiv 2024
-
[4]
N. Baˇ si´ c, P. W. Fowler and T. Pisanski, Vertex and edge orbits in nut graphs, Electron. J. Comb. 31 (2024), #P2.38
work page 2024
-
[5]
N. Baˇ si´ c, P. W. Fowler, T. Pisanski and I. Sciriha, On singular signed graphs with nullspace spanned by a full vector: Signed nut graphs, Discuss. Math. Graph Theory 42 (2022), 1351–1382
work page 2022
-
[6]
N. Baˇ si´ c, M. Knor and R.ˇSkrekovski, On 12-regular nut graphs, Art Discret. Appl. Math. 5 (2021), #P2.01
work page 2021
-
[7]
K. Coolsaet, P. W. Fowler and J. Goedgebeur, Generation and pr operties of nut graphs, MATCH Commun. Math. Comput. Chem. 80 (2018), 423–444
work page 2018
Show all 33 references
-
[8]
D. M. Cvetkovi´ c, M. Doob and H. Sachs, Spectra of graphs: Theory and applications , Leipzig: J. A. Barth Verlag, 1995
1995
-
[9]
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
-
[10]
Damnjanovi´ c, Two families of circulant nut graphs, Filomat 37 (2023), 8331–8360
I. Damnjanovi´ c, Two families of circulant nut graphs, Filomat 37 (2023), 8331–8360
2023
-
[11]
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 (2024), #P4.03
2024
-
[12]
Damnjanovi´ c, On the null spaces of quartic circulant grap hs, Discrete Math
I. Damnjanovi´ c, On the null spaces of quartic circulant grap hs, Discrete Math. Chem. (2025), in press
2025
-
[14]
Damnjanovi´ c and D
I. Damnjanovi´ c and D. Stevanovi´ c, On circulant nut graph s, Linear Algebra Appl. 633 (2022), 127–151
2022
-
[15]
Das and A
A. Das and A. Mandal, Classification of Cayley rose window graphs , Theory Appl. Graphs 8 (2021), Art. 7
2021
-
[16]
Dobson, I
E. Dobson, I. Kov´ acs and ˇS. Miklaviˇ c, The isomorphism problem for rose window graphs, Discrete Math. 323 (2014), 7–13
2014
-
[17]
Dobson, I
E. Dobson, I. Kov´ acs and ˇS. Miklaviˇ c, The automorphism groups of non-edge-transitive rose window graphs, Ars Math. Contemp. 9 (2015), 63–75
2015
-
[18]
Dobson, On automorphisms of Haar graphs of abelian groups , Art Discrete Appl
T. Dobson, On automorphisms of Haar graphs of abelian groups , Art Discrete Appl. Math 5 (2022), #P3.06
2022
-
[19]
Filaseta and A
M. Filaseta and A. Schinzel, On testing the divisibility of lacunary po lynomials by cyclo- tomic polynomials, Math. Comput. 73(246) (2003), 957–965
2003
-
[20]
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
2020
-
[21]
J. A. Gallian, Contemporary Abstract Algebra, 9th edition, Cengage Learning, 2017. 18
2017
-
[22]
Gao and Y
X. Gao and Y. Luo, The spectrum of semi-Cayley graphs over ab elian groups, Linear Algebra Appl. 432 (2010), 2974–2983
2010
-
[23]
J. L. Gross and T. W. Tucker, Topological Graph Theory, J. Wiley & Sons, 1987
1987
-
[24]
Guo and B
K. Guo and B. Mohar, Simple eigenvalues of cubic vertex-transit ive graphs, Canad. J. Math. 76 (2024), 1496–1519
2024
-
[25]
Hladnik, D
M. Hladnik, D. Maruˇ siˇ c and T. Pisanski, Cyclic Haar graphs, Discrete Math. 244 (2002), 137–152
2002
-
[26]
Kov´ acs, B
I. Kov´ acs, B. Kuzman, A. Malniˇ c and S. Wilson, Characteriza tion of edge-transitive 4- valent bicirculants, J. Graph Theory 69 (2012), 441–463
2012
-
[27]
Malniˇ c, D
A. Malniˇ c, D. Maruˇ siˇ c and P.ˇSparl, On strongly regular bicirculants, Eur. J. Comb. 28 (2007), 891–900
2007
-
[28]
Pisanski, A classification of cubic bicirculants, Discrete Math
T. Pisanski, A classification of cubic bicirculants, Discrete Math. 307 (2007), 567–578
2007
-
[29]
Sciriha and A
I. Sciriha and A. Farrugia, From Nut Graphs to Molecular Structure and Conductivity , vol. 23 of Mathematical Chemistry Monographs , University of Kragujevac, 2021
2021
-
[30]
Sciriha and I
I. Sciriha and I. Gutman, Nut graphs: Maximally extending cores , Util. Math. 54 (1998), 257–272
1998
-
[31]
Tattersall, Elementary number theory in nine chapters , Cambridge University Press, New York, 1999
J. Tattersall, Elementary number theory in nine chapters , Cambridge University Press, New York, 1999
1999
-
[32]
Wilson, Rose Window graphs, Ars
S. Wilson, Rose Window graphs, Ars. Math. Contemp. 1 (2008), 7–19
2008
-
[33]
The Sage Developers, SageMath, the Sage Mathematics Softw are System (Version 9.5), 2022, https://www.sagemath.org. 19 A SageMath script for Theorem 4.1 1 #!/usr/bin/sage 2 import sys 3 from sage.all import * 4 5 # R.<x> = PolynomialRing(QQ) 6 R = PolynomialRing(QQ, names=( ’x...
2022
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.