Pith. sign in

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 →

arxiv 2502.06353 v1 pith:FX7CWTZW submitted 2025-02-10 math.CO

classification math.CO MSC 05C5005C2505C75
keywords nutgraphbicirculantquarticspectrumcyclotomicpolynomiallacunaryRoseWindoweigenvaluezero
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Nut graphs are graphs whose zero eigenvalue is simple and whose corresponding eigenvector has no zero entries; they are of interest because the kernel then 'uses' every vertex. The paper asks which quartic bicirculants—connected 4-regular graphs admitting an automorphism with two vertex orbits of equal size—are nut graphs. It proves that the answer is completely finite: up to isomorphism, the nut graphs are exactly the graphs B1(m;a,b), B2(m;a,b,c), and B3(m;a,b) whose parameters satisfy explicit congruence and gcd conditions, and no graph from the fourth class B4 qualifies because those graphs are bipartite. If correct, the classification turns a spectral question into a small number of arithmetic checks and gives a complete structural description of all quartic bicirculant nut graphs.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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)
  1. [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.
  2. [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)
  1. [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.
  2. [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.
  3. [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.
  4. [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

0 steps flagged · score 2.0 of 10

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 0 free parameters · 7 assumptions · 0 invented entities

No fitted parameters appear; the classification is parametrized by integers m,a,b,c whose ranges are enumerated by the theorem conditions. The proof rests on standard external theorems plus the four-class decomposition and the B3 normalization isomorphisms, and on the B1 computational tables from [13].

assumptions (7)
  • standard math Cyclotomic polynomials Phi_f are irreducible over Q
    Used throughout Section 2.3 to convert root-of-unity equations into polynomial divisibility conditions; standard.
  • domain assumption Theorem 2.5 spectral formula for BiCirc(m;S,T,R)
    Cited from [22, Theorem 3.2]; it is the spectral decomposition that grounds Corollary 2.6, the central reduction that 0 being an eigenvalue is equivalent to |lambda^R|^2 = lambda^S lambda^T.
  • standard math Lemma 2.3: a simple eigenvector is constant or alternating on automorphism orbits
    Cited from [8, p. 135]; used in Lemma 2.4 to connect zero eigenvalue simplicity to full eigenvectors in bicirculants.
  • standard math Filaseta-Schinzel theorem on lacunary polynomials divisible by cyclotomic polynomials
    External theorem [19, Theorem 2] used in Lemmas 3.6 and 4.7 to reduce infinitely many possible f to a finite list.
  • domain assumption Four-class decomposition of connected quartic bicirculants
    From [26]; the entire proof assumes every connected quartic bicirculant is one of B1-B4 with |R|=1,2,3,4, and identifies B4 graphs as cyclic Haar graphs.
  • domain assumption B3(m;a,b) isomorphism normalization: isomorphic to B3(m;-a,b-a) and B3(m;-b,a-b)
    Stated in Section 1 without proof; it is load-bearing because it justifies the WLOG that a,b have the same parity, and Theorem 5.1 only covers that case.
  • domain assumption Correctness of the B1 finite computational checks in [13, Sections A and B]
    The sufficiency proof of Theorem 3.1 asserts no Phi_f divides the reduced polynomials for f in the finite list; this is cited rather than demonstrated in this paper.

how reviews work

0 comments
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

Figures reproduced from arXiv: 2502.06353 by the authors.

Figure 1
Figure 1. Possible Zm-voltage graphs for the connected quartic bicirculants. Cases (1) and (3) occur only when m is even and in this case, the voltages on the semi-edges are equal to m 2 . Note that these four classes are not disjoint. For example, B2(4; 1, 1, 2) ∈ B2 is isomorphic to B4(4; 1, 2, 3) ∈ B4, and B2(6; 1, 1, 3) ∈ B2 is isomorphic to B3(6; 1, 5) ∈ B3; see [26]. The graphs from B4 (with |R| = 4) are known as the cy… view at source ↗
Figure 2
Figure 2. The smallest examples of QBN graphs. Kernel eigenvector [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [13]

    Damnjanovi´ c, N

    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

  2. [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

  3. [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

  4. [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

  5. [4]

    Baˇ si´ c, P

    N. Baˇ si´ c, P. W. Fowler and T. Pisanski, Vertex and edge orbits in nut graphs, Electron. J. Comb. 31 (2024), #P2.38

  6. [5]

    Baˇ si´ c, P

    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

  7. [6]

    Baˇ si´ c, M

    N. Baˇ si´ c, M. Knor and R.ˇSkrekovski, On 12-regular nut graphs, Art Discret. Appl. Math. 5 (2021), #P2.01

  8. [7]

    Coolsaet, P

    K. Coolsaet, P. W. Fowler and J. Goedgebeur, Generation and pr operties of nut graphs, MATCH Commun. Math. Comput. Chem. 80 (2018), 423–444

Show all 33 references
  1. [8]

    D. M. Cvetkovi´ c, M. Doob and H. Sachs, Spectra of graphs: Theory and applications , Leipzig: J. A. Barth Verlag, 1995

  2. [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]

  3. [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

  4. [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

  5. [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

  6. [14]

    Damnjanovi´ c and D

    I. Damnjanovi´ c and D. Stevanovi´ c, On circulant nut graph s, Linear Algebra Appl. 633 (2022), 127–151

  7. [15]

    Das and A

    A. Das and A. Mandal, Classification of Cayley rose window graphs , Theory Appl. Graphs 8 (2021), Art. 7

  8. [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

  9. [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

  10. [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

  11. [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

  12. [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

  13. [21]

    J. A. Gallian, Contemporary Abstract Algebra, 9th edition, Cengage Learning, 2017. 18

  14. [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

  15. [23]

    J. L. Gross and T. W. Tucker, Topological Graph Theory, J. Wiley & Sons, 1987

  16. [24]

    Guo and B

    K. Guo and B. Mohar, Simple eigenvalues of cubic vertex-transit ive graphs, Canad. J. Math. 76 (2024), 1496–1519

  17. [25]

    Hladnik, D

    M. Hladnik, D. Maruˇ siˇ c and T. Pisanski, Cyclic Haar graphs, Discrete Math. 244 (2002), 137–152

  18. [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

  19. [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

  20. [28]

    Pisanski, A classification of cubic bicirculants, Discrete Math

    T. Pisanski, A classification of cubic bicirculants, Discrete Math. 307 (2007), 567–578

  21. [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

  22. [30]

    Sciriha and I

    I. Sciriha and I. Gutman, Nut graphs: Maximally extending cores , Util. Math. 54 (1998), 257–272

  23. [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

  24. [32]

    Wilson, Rose Window graphs, Ars

    S. Wilson, Rose Window graphs, Ars. Math. Contemp. 1 (2008), 7–19

  25. [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...

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.