pith. sign in

arxiv: 2605.02711 · v2 · submitted 2026-05-04 · 🧮 math.CO

Factorization of invariant polynomials and generalized spectral characterizations of graphs

Wei Wang , Quanyu Tang This is my paper

Pith reviewed 2026-05-08 18:20 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C50
keywords generalized spectrumDGS graphsinvariant polynomialwalk matrixrooted productadjacency operatorspectral characterizationfinite field
0
0 comments X

The pith

The square-root polynomial of the invariant polynomial Φ_p(G;x) can replace its square-free part to give a stronger criterion for a graph to be determined by its generalized spectrum.

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

This paper proves a conjecture asserting that the square-root polynomial of Φ_p(G;x) yields a more effective test than the square-free part for whether a graph is determined by its generalized spectrum. The proof proceeds by establishing an algebraic factorization of Φ_p(G;x) as the product of the characteristic polynomial of the adjacency operator restricted to the left null space of the walk matrix and the characteristic polynomial of the adjacency operator restricted to the radical of that space. With this factorization in hand, the authors construct a broad family of graphs that satisfy the refined DGS criterion through rooted products, extending earlier constructions.

Core claim

We show that Φ_p(G;x) factors as the product of the characteristic polynomial of the adjacency operator on the left null space of the walk matrix and the characteristic polynomial of the adjacency operator on the radical of that null space. This identity implies that the square-root polynomial of Φ_p(G;x) serves as a valid and stronger replacement for the square-free part in the DGS criterion, and it yields a large new family of DGS graphs obtained by taking rooted products.

What carries the argument

The algebraic factorization of the invariant polynomial Φ_p(G;x) into the product of two characteristic polynomials of the adjacency operator (one on the left null space of the walk matrix and one on its radical).

If this is right

  • The square-root polynomial of Φ_p(G;x) supplies a strictly stronger DGS criterion than the square-free part for arbitrary graphs.
  • Rooted products can be used to generate an infinite family of DGS graphs that properly contains all previously known examples obtained by the same method.
  • The factorization supplies an explicit algebraic decomposition that can be used to compute or simplify the invariant polynomial for any given graph.
  • Any graph whose walk matrix has a trivial radical will have Φ_p(G;x) equal to a single characteristic polynomial, simplifying the DGS test.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same factorization technique could be applied to other invariant polynomials defined over finite fields to obtain analogous refinements of spectral criteria.
  • One could implement the factorization in a computer algebra system and systematically enumerate small DGS graphs that were previously undetected by the square-free test.
  • The construction via rooted products suggests that DGS graphs may be closed under certain grafting operations, opening a route to inductive proofs for larger families.

Load-bearing premise

The stated algebraic factorization of Φ_p(G;x) holds for every graph when the walk matrix, its left null space, and the radical are defined over the field F_p.

What would settle it

A concrete small graph on which direct computation shows that the square-root polynomial of Φ_p(G;x) fails to match the DGS status predicted by the factorization, or on which the factorization itself does not hold.

read the original abstract

The problem of characterizing graphs by their generalized spectra has received significant attention in recent years. This paper provides a complete proof of a conjecture proposed by Wang, Wang, and Zhu (European J. Combin., 2023), which asserts that the square-root polynomial of the invariant polynomial $\Phi_p(G;x) \in \mathbb{F}_p[x]$ can replace its square-free part to yield a more effective criterion for a graph to be determined by its generalized spectrum (DGS). A key ingredient of our proof is a novel algebraic factorization: we show that the polynomial $\Phi_p(G;x)$ is the product of the characteristic polynomials of the adjacency operator restricted to the left null space of the walk matrix and its radical, respectively. Based on this refined DGS-criterion, a broad family of DGS-graphs is constructed via rooted products, significantly generalizing the recent result of Wang, Shen, and Mao (Discrete Appl. Math., 2026).

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 / 2 minor

Summary. The manuscript proves the conjecture of Wang, Wang, and Zhu (European J. Combin. 2023) asserting that the square-root polynomial of the invariant polynomial Φ_p(G;x) ∈ F_p[x] yields a strictly stronger criterion for a graph to be determined by its generalized spectrum (DGS) than the square-free part. The proof rests on a new algebraic factorization: Φ_p(G;x) equals the product of the characteristic polynomials of the adjacency operator A restricted to the left nullspace N of the walk matrix and to the radical R of the relevant module. The authors then apply the refined criterion to construct an infinite family of DGS graphs by iterated rooted products, generalizing the constructions of Wang, Shen, and Mao (Discrete Appl. Math. 2026).

Significance. If the factorization identity holds for arbitrary graphs, the work supplies both a sharper theoretical test for DGS graphs and explicit, scalable constructions that enlarge the known families. The algebraic decomposition itself is a technical contribution that may find use beyond the DGS problem.

major comments (1)
  1. [§3] §3 (factorization theorem): The identity Φ_p(G;x) = χ(A|_N;x) · χ(A|_R;x) requires that the ambient F_p-module V decomposes as the direct sum N ⊕ R with both summands A-invariant. The manuscript must supply an explicit verification that A(R) ⊆ R, that N ∩ R = {0}, and that N + R = V, without additional hypotheses such as connectedness of G or p not dividing |V(G)|. If any of these fail for some graphs, the factorization does not hold universally and the refined DGS criterion is not available for those graphs.
minor comments (2)
  1. The preliminary section should include a self-contained definition of the radical R (of the image of the walk matrix or of the module generated by walks) together with the precise action of A on it.
  2. Notation for the left nullspace of the walk matrix and for the square-root polynomial should be introduced once and used consistently; occasional shifts between Φ_p^{1/2} and √Φ_p are distracting.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for pointing out the need for an explicit verification of the direct-sum decomposition underlying the factorization theorem. We address the comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§3] §3 (factorization theorem): The identity Φ_p(G;x) = χ(A|_N;x) · χ(A|_R;x) requires that the ambient F_p-module V decomposes as the direct sum N ⊕ R with both summands A-invariant. The manuscript must supply an explicit verification that A(R) ⊆ R, that N ∩ R = {0}, and that N + R = V, without additional hypotheses such as connectedness of G or p not dividing |V(G)|. If any of these fail for some graphs, the factorization does not hold universally and the refined DGS criterion is not available for those graphs.

    Authors: We agree that the factorization identity depends on V = N ⊕ R with both summands A-invariant and that these properties must be stated and proved explicitly for the result to apply to arbitrary graphs. The current manuscript derives the factorization from the definitions of the left nullspace N of the walk matrix and the radical R but does not isolate the three required verifications (A-invariance of R, trivial intersection, and spanning) as a standalone lemma. In the revised version we will insert a new Lemma 3.1 immediately before the factorization theorem. The lemma will prove, using only the module-theoretic definitions and without assuming connectedness of G or that p does not divide n, that (i) A(R) ⊆ R, (ii) N ∩ R = {0}, and (iii) N + R = V. This addition will confirm that the factorization holds universally and will thereby make the refined DGS criterion available for all graphs. revision: yes

Circularity Check

0 steps flagged

No significant circularity; novel factorization independently proves prior conjecture

full rationale

The paper introduces a novel algebraic factorization of the invariant polynomial Φ_p(G;x) as the product of characteristic polynomials of the adjacency operator restricted to the left null space of the walk matrix and its radical. This is presented as a key independent ingredient used to prove the DGS conjecture from Wang-Wang-Zhu (2023). The factorization is derived from the algebraic definitions of the walk matrix, null space, and radical over F_p for arbitrary graphs, without reducing to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The conjecture itself is the target result being proved rather than an assumed premise, and the rooted-product construction generalizes prior work without circular dependence on the new result. The derivation chain remains self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard algebraic facts about polynomials and linear operators over finite fields together with the definitions of the walk matrix and adjacency operator; no free parameters are fitted, and no new entities are postulated.

axioms (2)
  • standard math Standard properties of characteristic polynomials of linear operators on finite-dimensional vector spaces over finite fields F_p.
    Used to define and multiply the two factors in the claimed factorization of Φ_p(G;x).
  • domain assumption The walk matrix and its left null space are well-defined for the adjacency operator of any graph.
    Invoked when restricting the adjacency operator to the left null space.

pith-pipeline@v0.9.0 · 5457 in / 1565 out tokens · 86778 ms · 2026-05-08T18:20:05.191793+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

20 extracted references · 20 canonical work pages

  1. [1]

    Cvetkovi´ c, P

    D. Cvetkovi´ c, P. Rowlinson, S. Simi´ c, An Introduction to the Theory of Graph Spectra, Cambridge, Cambridge University Press, UK, 2010

    work page 2010

  2. [2]

    F. Q. Gouvˆ ea,p-adic Numbers, 3rd ed., Springer, 2020

    work page 2020

  3. [3]

    C. D. Godsil, B. D. McKay, Spectral conditions for the reconstructibility of a graph, J. Combin. Theory, Ser. B 30 (1981) 285–289

    work page 1981

  4. [4]

    C. D. Godsil, Controllable subsets in graphs. Ann. Combin. 16(4) (2012) 733–744

    work page 2012

  5. [5]

    von zur Gathen, J

    J. von zur Gathen, J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, Cambridge, 2013

    work page 2013

  6. [6]

    S. Guo, W. Wang, W. Wang, Primary decomposition theorem and generalized spectral characterization of graphs, Adv. Appl. Math. 170 (2025) 102927

    work page 2025

  7. [7]

    C. R. Johnson, M. Newman, A note on cospectral graphs, J. Combin. Theory, Ser. B 28 (1980) 96–103

    work page 1980

  8. [8]

    D. A. Harville, Matrix Algebra From a Statistician’s Perspective, Springer, 2008

    work page 2008

  9. [9]

    F. Liu, J. Siemons, W. Wang, New families of graphs determined by their generalized spec- trum, Discrete Math. 342 (2019) 1108–1112

    work page 2019

  10. [10]

    F. Liu, J. Siemons, Unlocking the walk matrix of a graph, J. Algebraic Combin. 55 (2022) 663–690

    work page 2022

  11. [11]

    L. Qiu, W. Wang, W. Wang, H. Zhang, Smith Normal Form and the generalized spectral characterization of graphs, Discrete Math. 346 (2023) 113177

    work page 2023

  12. [12]

    Rowlinson, The main eigenvalues of a graph: a survey, Appl

    P. Rowlinson, The main eigenvalues of a graph: a survey, Appl. Anal. Discrete Math. 1 (2007) 445–471

    work page 2007

  13. [13]

    Roman, Advanced Linear Algebra, 3rd ed., volume 135 of Graduate Texts in Mathemat- ics

    S. Roman, Advanced Linear Algebra, 3rd ed., volume 135 of Graduate Texts in Mathemat- ics. Springer, New York, 2008

    work page 2008

  14. [14]

    Wang, On the Smith normal form of walk matrices, Linear Algebra Appl

    W. Wang, On the Smith normal form of walk matrices, Linear Algebra Appl. 612 (2021) 30–41

    work page 2021

  15. [15]

    Wang, A simple arithmetic criterion for graphs being determined by their generalized spectra, J

    W. Wang, A simple arithmetic criterion for graphs being determined by their generalized spectra, J. Combin. Theory, Ser. B 122 (2017) 438–451

    work page 2017

  16. [16]

    Wang, Generalized spectral characterization revisited, Electron

    W. Wang, Generalized spectral characterization revisited, Electron. J. Combin. 20 (4) (2013) #P4. 14

    work page 2013

  17. [17]

    W. Wang, J. Shen, L. Mao, A general formula for walk determinants of rooted products with applications to DGS-graph constructions, Discrete Appl. Math. 390 (2026) 220-230

    work page 2026

  18. [18]

    Wang, C.-X

    W. Wang, C.-X. Xu, A sufficient condition for a family of graphs being determined by their generalized spectra, European J. Combin. 27 (2006) 826–840

    work page 2006

  19. [19]

    W. Wang, W. Wang, F. Zhu, An improved condition for a graph to be determined by its generalized spectrum, European J. Combin. 108 (2023) 103638

    work page 2023

  20. [20]

    W. Wang, Z. Yan, L. Mao, Proof of a conjecture on the determinant of the walk matrix of rooted product with a path, Linear Multilinear Algebra 72 (5) (2024) 828–840. 15

    work page 2024