pith. sign in

arxiv: 2606.13510 · v1 · pith:XDEULZIEnew · submitted 2026-06-11 · 🧮 math.CO

Wang-Qiu-Hu switching and isomorphism

Aida Abiad , Hong-Jun Ge This is my paper

Pith reviewed 2026-06-27 06:17 UTC · model grok-4.3

classification 🧮 math.CO
keywords WQH-switchingcospectral graphscommon-neighbour multisetsgraph isomorphismclique extensionsweak tensor productsLaplacian matrices
0
0 comments X

The pith

Common-neighbour multisets certify non-isomorphism after WQH-switching.

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

Cospectral graphs share the same eigenvalues yet may still be non-isomorphic, and switching constructions that preserve the spectrum do not automatically guarantee distinct graphs. The paper derives a criterion that checks the multisets of common neighbours attached to the vertices of a WQH partition; these multisets are preserved by isomorphism but can differ after switching. When the multisets differ, the switched graphs are certified non-isomorphic without further appeal to the spectrum. The criterion is applied to clique extensions and weak tensor products (including coclique extensions) to produce infinite families of cospectral non-isomorphic graphs, and the switching operation itself is extended to generalized adjacency matrices and, under a degree condition, to Laplacian and signless-Laplacian matrices.

Core claim

The common-neighbour multisets associated with a WQH partition supply an isomorphism-invariant independent of the spectrum that is sufficient to certify non-isomorphism for the switched graphs. This invariant is applied to clique extensions and to weak tensor products, with coclique extensions as a special case, yielding infinite families of cospectral non-isomorphic graphs. The conditions for WQH-switching are further extended to generalized adjacency matrices and, under an additional degree condition, to the Laplacian and signless-Laplacian matrices.

What carries the argument

The external common-neighbour criterion formed from the multisets of common neighbours for the vertices in a WQH partition.

If this is right

  • The criterion applies directly to clique extensions and produces cospectral non-isomorphic graphs.
  • The criterion applies to weak tensor products and to coclique extensions as a special case.
  • Infinite families of cospectral non-isomorphic graphs are obtained from these constructions.
  • WQH-switching extends to generalized adjacency matrices.
  • Under an added degree condition, WQH-switching preserves Laplacian and signless-Laplacian spectra.

Where Pith is reading between the lines

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

  • The same multisets could be checked on cospectral pairs arising from other switching operations to test whether they distinguish those graphs as well.
  • Implementation of the multiset comparison on larger graphs might provide a practical supplement to spectral methods when isomorphism testing is required.
  • The extension to Laplacian matrices suggests the criterion may adapt to other algebraic graph invariants under suitable degree or regularity assumptions.

Load-bearing premise

The common-neighbour multisets tied to a WQH partition are preserved exactly when two graphs are isomorphic and can differ after switching in a way that proves the graphs are distinct.

What would settle it

Two graphs related by WQH-switching that have different common-neighbour multisets for the partition yet are isomorphic would falsify the claim that differing multisets certify non-isomorphism.

read the original abstract

Cospectral graphs (graphs that share the same eigenvalues) expose the limitations of using the graph spectrum to uniquely identify graphs, and they also help to understand what structural properties a graph spectrum cannot capture. Switching methods, which are standard tools for constructing cospectral graphs, require specific structural and algebraic conditions to hold for the operation to preserve the graph's spectrum. However, there is no guarantee that the obtained cospectral switched graph is non-isomorphic. In this paper we study this isomorphism problem for a recent and prolific switching method to produce cospectral graphs with respect to the adjacency spectra: Wang-Qiu-Hu (WQH) switching. We do so by using common-neighbour multisets associated with a WQH partition, which allows us to derive an external common-neighbour criterion for certifying non-isomorphism after WQH-switching. Then, we apply the new criterion to clique extensions and to weak tensor products, with coclique extensions as a special case. As an application we obtain infinite families of cospectral non-isomorphic graphs, including some known constructions. Finally we extend the conditions of WQH-switching to generalized adjacency matrices and, under an additional degree condition, to Laplacian and signless Laplacian matrices.

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

0 major / 3 minor

Summary. The paper derives a criterion based on common-neighbour multisets tied to a WQH partition that serves as an isomorphism invariant independent of the spectrum, allowing certification of non-isomorphism for graphs obtained by WQH-switching. The criterion is applied to clique extensions and weak tensor products (with coclique extensions as a special case) to produce infinite families of cospectral non-isomorphic graphs; the switching conditions are also extended to generalized adjacency matrices and, under an extra degree condition, to the Laplacian and signless Laplacian.

Significance. If the criterion holds, the work supplies a concrete external invariant for distinguishing cospectral graphs produced by WQH-switching, a recent construction method. The explicit applications yield infinite families (including recoveries of known examples) and the matrix extensions broaden the scope. The independence from the spectrum is a clear strength, as is the focus on verifiable structural conditions rather than fitted parameters.

minor comments (3)
  1. [§2] §2: the precise definition of the WQH partition and the associated common-neighbour multiset would benefit from an explicit small example (e.g., a 6- or 8-vertex graph) to illustrate how the multiset is computed and why it is preserved under isomorphism but altered by the switch.
  2. [§4.2] §4.2 (weak tensor product application): the statement that the criterion certifies non-isomorphism for all members of the infinite family should include a brief verification that the degree condition required for the Laplacian extension is satisfied in this construction.
  3. The paper would be strengthened by a short table or remark comparing the new common-neighbour criterion with existing invariants (e.g., the number of common neighbours or the Seidel switching criterion) on the same families.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work on the common-neighbour criterion for WQH-switching and its applications to infinite families of cospectral graphs, as well as the extensions to other matrices. The recommendation of minor revision is noted. However, the report lists no specific major comments, so we have no points requiring response or revision at this time.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives an external common-neighbour multiset criterion tied to WQH partitions to certify non-isomorphism of switched graphs, explicitly positioned as independent of the spectrum. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the invariant is introduced via direct structural association with the partition and applied to extensions without renaming known results or smuggling ansatzes. The derivation remains self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper operates entirely within standard spectral graph theory; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • standard math Standard assumptions of spectral graph theory: adjacency matrices are symmetric 0-1 matrices with eigenvalues determining cospectrality, and switching preserves the spectrum under stated partition conditions.
    Invoked throughout the description of WQH switching and the common-neighbour criterion.

pith-pipeline@v0.9.1-grok · 5733 in / 1198 out tokens · 20830 ms · 2026-06-27T06:17:19.611284+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

21 extracted references

  1. [1]

    Abiad, B

    A. Abiad, B. Brimkov, J. Breen, T. R. Cameron, H. Gupta, and R. R. Villagr´ an. Con- structions of cospectral graphs with different zero forcing numbers.Electron. J. Linear Algebra, 38:280–294, 2022

    2022

  2. [2]

    Abiad, A

    A. Abiad, A. E. Brouwer, and W. H. Haemers. Godsil-McKay switching and isomorphism. Electron. J. Linear Algebra, 28:4–11, 2015

    2015

  3. [3]

    Abiad, J

    A. Abiad, J. D’haeseleer, W. H. Haemers, and R. Simoens. Cospectral mates for generalized Johnson and Grassmann graphs.Linear Algebra Appl., 678:1–15, 2023

    2023

  4. [4]

    Abiad and W

    A. Abiad and W. H. Haemers. Cospectral graphs and regular orthogonal matrices of level 2.Electron. J. Comb., 19:#P13, 2012

    2012

  5. [5]

    Abiad, N

    A. Abiad, N. van de Berg, and R. Simoens. Counting cospectral graphs obtained via switching.Discrete Math., 349(3):114775, 2026

    2026

  6. [6]

    Abiad, N

    A. Abiad, N. van de Berg, and R. Simoens. Switching methods of level 2 for the construc- tion of cospectral graphs.Linear Algebra Appl., to appear, 2026. 17

    2026

  7. [7]

    Z. L. Bl´ azsik, J. Cummings, and W. H. Haemers. Cospectral regular graphs with and without a perfect matching.Discrete Math., 338(3):199–201, 2015

    2015

  8. [8]

    R. J. Evans, S. Goryainov, E. V. Konstantinova, and A. D. Mednykh. A general construc- tion of strictly neumaier graphs and a related switching.Discrete Math., 346(7):113384, 2023

    2023

  9. [9]

    C. D. Godsil and B. D. McKay. Constructing cospectral graphs.Aequationes Math., 25(2-3):257–268, 1982

    1982

  10. [10]

    W. H. Haemers. Distance-regularity and the spectrum of graphs.Linear Algebra Appl., 236:265–278, 1996

    1996

  11. [11]

    W. H. Haemers. Cospectral pairs of regular graphs with different connectivity.Discuss. Math. Graph Theory, 40:577–584, 2020

    2020

  12. [12]

    Ihringer

    F. Ihringer. Switching for small strongly regular graphs.Australas. J. Combin., 84:28–48, 2022

    2022

  13. [13]

    Ihringer and A

    F. Ihringer and A. Munemasa. New strongly regular graphs from finite geometries via switching.Linear Algebra Appl., 580:464–474, 2019

    2019

  14. [14]

    Ihringer, F

    F. Ihringer, F. Pavese, and V. Smaldore. Graphs cospectral withN U(n+ 1, q 2),n̸= 3. Discrete Math., 344(11):112560, 2021

    2021

  15. [15]

    Ihringer and R

    F. Ihringer and R. Simoens. Design switching on graphs.arXiv, 2508.11523, 2025

    arXiv 2025

  16. [16]

    L. Mao, W. Wang, F. Liu, and L. Qiu. Constructing cospectral graphs via regular rational orthogonal matrices with level two.Discrete Math., 346(1):113156, 2023

    2023

  17. [17]

    L. Qiu, Y. Ji, and W. Wang. On a theorem of godsil and mckay concerning the construction of cospectral graphs.Linear Algebra Appl., 603:265–274, 2020

    2020

  18. [18]

    L. Qiu, Y. Ji, and W. Wang. On a theorem of Godsil and McKay concerning the construc- tion of cospectral graphs.Linear Algebra Appl., 603:265–274, 2020

    2020

  19. [19]

    E. R. van Dam, H.-J. Ge, and J. H. Koolen. Co-edge-regular four-eigenvalue graphs with unbounded coherent rank.work in progress, 2026

    2026

  20. [20]

    E. R. van Dam and W. H. Haemers. Which graphs are determined by their spectrum?Lin- ear Algebra Appl., 373:241–272, 2003. Combinatorial Matrix Theory Conference (Pohang, 2002)

    2003

  21. [21]

    W. Wang, L. Qiu, and Y. Hu. Cospectral graphs, GM-switching and regular rational orthogonal matrices of levelp.Linear Algebra Appl., 563:154–177, 2019. 18

    2019