pith. sign in

arxiv: 2601.01482 · v2 · submitted 2026-01-04 · 🧮 math.CO

Subcubic graphs without eigenvalues in (-1, 1)

Shenwei Huang , Zilin Jiang This is my paper

Pith reviewed 2026-05-16 17:51 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C50
keywords subcubic graphseigenvaluesspectral gapgraph classificationadjacency spectrumcubic graphs
0
0 comments X

The pith

Connected subcubic graphs without eigenvalues in (-1,1) consist of two infinite families and seven sporadic examples at most 18 vertices large.

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

The paper finishes classifying all connected subcubic graphs with no adjacency eigenvalues in the interval from -1 to 1. Previous work covered the cubic ones, so this handles the cases with maximum degree 3 but not all vertices degree 3. It finds exactly two infinite families together with seven small sporadic graphs. This proves that the open interval (-1,1) is a maximal spectral gap for the whole class of connected subcubic graphs. Readers care as it shows how limited the structures are that can have this spectral property.

Core claim

We show that exactly two infinite families and seven sporadic examples occur, and that every sporadic graph has at most 18 vertices. As a consequence, (-1,1) is a maximal spectral gap set for the class of connected subcubic graphs.

What carries the argument

The complete list of non-cubic connected subcubic graphs avoiding eigenvalues in (-1,1), obtained via structural analysis and exhaustive enumeration up to 18 vertices.

Load-bearing premise

That no additional infinite families or larger sporadic graphs without eigenvalues in (-1,1) exist beyond those found.

What would settle it

A connected subcubic graph with 19 or more vertices, not in the two families, that has no eigenvalues in the interval (-1,1) would contradict the classification.

Figures

Figures reproduced from arXiv: 2601.01482 by Shenwei Huang, Zilin Jiang.

Figure 1
Figure 1. Figure 1: Petersen graph, Heawood graph, M¨obius–Kantor graph, and Desargues graph [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Twisted ladder ▷◁n on n rungs, which has 4n vertices. 2 [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Bipartite graphs HJn without eigenvalues in (−1, 1). result on spectral gap sets. Corollary 1.2. The interval (−1, 1) ⊂ [−3, 3] is a maximal spectral gap set for the class of connected subcubic graphs. The remainder of the paper is organized as follows. In Section 2 we outline the main ideas and derive Theorem 1.1 and its spectral consequence Corollary 1.2. In Sections 3 and 4 we treat the bipartite case o… view at source ↗
Figure 4
Figure 4. Figure 4: Non-bipartite graphs HJ′ n without eigenvalues in (−1, 1). 3 [PITH_FULL_IMAGE:figures/full_fig_p003_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Rooted multigraphs whose associated matrices are not positive semidefinite. Solid circles [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Sporadic bipartite graphs HJ+ 1 and HJ+ 2 of girth 4 without eigenvalues in (−1, 1). Lemma 2.9. For every rooted graph GR, the associated matrix of GR is positive semidefinite if and only if, for every n ∈ N, the graph GR + Kn has smallest eigenvalue at least −2, where the graph GR + Kn is obtained from G by attaching a copy of the clique Kn of order n to each root in R. Proof. Let M be the associated matr… view at source ↗
Figure 7
Figure 7. Figure 7: Sporadic bipartite graphs of girth 6 without eigenvalues in ( [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The nine minimal forbidden induced subgraphs for line graphs. [PITH_FULL_IMAGE:figures/full_fig_p015_8.png] view at source ↗
read the original abstract

Guo and Royle recently classified the connected cubic graphs without eigenvalues of their adjacency matrix in the open interval $(-1, 1)$, and raised the question of extending their classification to graphs of maximum degree at most $3$. They carried out a preliminary investigation of the subcubic case, exhibiting both infinite families and sporadic examples. In this paper, we complete this investigation by determining all connected subcubic graphs that are not cubic and have no eigenvalues in $(-1,1)$. We show that exactly two infinite families and seven sporadic examples occur, and that every sporadic graph has at most $18$ vertices. As a consequence, we prove that $(-1,1)$ is a maximal spectral gap set for the class of connected subcubic graphs. Guo and Royle, answering a question of Koll\'ar and Sanark, established this maximality for connected cubic graphs. Our result generalizes their conclusion to the subcubic setting.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 3 minor

Summary. The manuscript classifies all connected subcubic graphs (maximum degree ≤3) whose adjacency matrices have no eigenvalues in the open interval (-1,1). It identifies exactly two infinite families together with seven sporadic examples, each on at most 18 vertices. As a direct consequence, (-1,1) is shown to be a maximal spectral gap set for the class of all connected subcubic graphs, extending the cubic-graph result of Guo and Royle.

Significance. If the classification holds, the result supplies a complete, explicit description of the subcubic graphs avoiding eigenvalues in (-1,1), with concrete infinite families and a sharp bound on the size of exceptions. This generalizes the cubic case and yields a clean maximality statement for the spectral gap, which is useful for further work on eigenvalue gaps in bounded-degree graphs. The standard combination of structural families plus bounded enumeration is executed here without introducing free parameters or ad-hoc reductions.

major comments (1)
  1. [§4] §4 (enumeration step): the claim that the seven sporadic graphs are the only ones up to 18 vertices rests on an exhaustive computer search; the manuscript must state the precise algorithm, the software used, and the verification that every connected subcubic graph on ≤18 vertices was tested for eigenvalues in (-1,1). This check is load-bearing for the “exactly seven” assertion.
minor comments (3)
  1. [§3] The statement of the two infinite families would be clearer if their adjacency matrices or characteristic polynomials were displayed explicitly in a single proposition.
  2. [Table 1] Table 1 (list of sporadic graphs) should include the exact number of vertices and the multiplicity of eigenvalue 0 for each example to facilitate independent verification.
  3. [§5] A brief remark on why the maximality proof does not extend immediately to disconnected graphs would avoid a minor scope ambiguity in the final corollary.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for the constructive suggestion regarding the enumeration procedure. We address the single major comment below.

read point-by-point responses

  1. Referee: [§4] §4 (enumeration step): the claim that the seven sporadic graphs are the only ones up to 18 vertices rests on an exhaustive computer search; the manuscript must state the precise algorithm, the software used, and the verification that every connected subcubic graph on ≤18 vertices was tested for eigenvalues in (-1,1). This check is load-bearing for the “exactly seven” assertion.

    Authors: We agree that the current description of the enumeration in §4 is insufficiently detailed. In the revised manuscript we will expand this section to specify the exact algorithm (a depth-first generation of all connected graphs with maximum degree 3, filtered by connectivity and order), the software employed (SageMath 9.5 together with its nauty interface for isomorphism-free generation), and the verification steps (eigenvalue computation via numpy.linalg.eigvals on the adjacency matrix for each generated graph, followed by an explicit interval check). We will also note that the search was run exhaustively for all orders from 1 to 18 and that the seven graphs listed are the only ones satisfying the spectral condition. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation proceeds by structural arguments that extend the independent classification of cubic graphs by Guo and Royle (external citation) to the subcubic non-cubic case. The two infinite families and seven sporadic examples are identified via case analysis on maximum degree 3 graphs, with an exhaustive bound of 18 vertices established by direct verification rather than any fitted parameter or self-referential definition. The maximality of the spectral gap (-1,1) follows immediately from the completeness of this list without reducing any new claim to a prior result by the same authors or to an input by construction. No load-bearing step matches any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard facts about real symmetric matrices, the interlacing theorem for induced subgraphs, and the known cubic classification; no new free parameters or invented entities are introduced.

axioms (2)
  • standard math Adjacency matrix of an undirected graph is real symmetric, hence has real eigenvalues
    Invoked implicitly throughout the spectral analysis
  • standard math Eigenvalue interlacing holds for induced subgraphs
    Used to bound possible eigenvalues in small graphs

pith-pipeline@v0.9.0 · 5451 in / 1232 out tokens · 55726 ms · 2026-05-16T17:51:33.097066+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · 2 internal anchors

  1. [1]

    Median eigenvalues of subcubic graphs, 2025

    Hricha Acharya, Benjamin Jeter, and Zilin Jiang. Median eigenvalues of subcubic graphs, 2025. arXiv:2502.13139 [math.CO]

    work page arXiv 2025

  2. [2]

    Lowell W. Beineke. Characterizations of derived graphs. J. Combinatorial Theory , 9:129–135, 1970

    work page 1970

  3. [3]

    P. J. Cameron, J.-M. Goethals, J. J. Seidel, and E. E. Shult. Line graphs, root systems, and elliptic geometry. J. Algebra, 43(1):305–327, 1976. 30

    work page 1976

  4. [4]

    Large regular bipartite graphs with median eigenvalue 1

    Krystal Guo and Bojan Mohar. Large regular bipartite graphs with median eigenvalue 1. Linear Algebra Appl., 449:68–75, 2014. arXiv:1309.7025 [math.CO]

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  5. [5]

    Krystal Guo and Gordon F. Royle. Cubic graphs with no eigenvalues in the interval ( −2, 0),

    work page

  6. [6]

    arXiv:2506.05861 [math.CO]

    work page arXiv

  7. [7]

    Krystal Guo and Gordon F. Royle. Cubic graphs with no eigenvalues in the interval ( −1, 1). J. Combin. Theory Ser. B , 176:561–583, 2026. arXiv:2409.02678 [math.CO]

    work page arXiv 2026

  8. [8]

    Alan J. Hoffman. On graphs whose least eigenvalue exceeds −1 − √

    work page

  9. [9]

    Linear Algebra Appl., 16(2):153–165, 1977

    work page 1977

  10. [10]

    Multiple Kronecker covering graphs.European J

    Wilfried Imrich and Tomaˇ z Pisanski. Multiple Kronecker covering graphs.European J. Combin., 29(5):1116–1122, 2008. arXiv:0505135 [math.CO]

    work page 2008

  11. [11]

    Koll´ ar and Peter Sarnak

    Alicia J. Koll´ ar and Peter Sarnak. Gap sets for the spectra of cubic graphs. Commun. Am. Math. Soc., 1:1–38, 2021. arXiv:2005.05379 [math-ph]

    work page arXiv 2021

  12. [12]

    Median eigenvalues of bipartite subcubic graphs

    Bojan Mohar. Median eigenvalues of bipartite subcubic graphs. Combin. Probab. Comput., 25(5):768–790, 2016. arXiv:1309.7395 [math.CO]

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  13. [13]

    Congruent Graphs and the Connectivity of Graphs

    Hassler Whitney. Congruent Graphs and the Connectivity of Graphs. Amer. J. Math. , 54(1):150–168, 1932. 31

    work page 1932