pith. sign in

arxiv: 2410.07948 · v2 · submitted 2024-10-10 · 🧮 math.CO

Switching methods of level 2 for the construction of cospectral graphs

Aida Abiad , Nils van de Berg , Robin Simoens This is my paper

Pith reviewed 2026-05-23 18:55 UTC · model grok-4.3

classification 🧮 math.CO
keywords cospectral graphsswitching methodslevel 2regular orthogonal matricesreducibilitygraph spectraindecomposable blocksHaemers conjecture
0
0 comments X

The pith

Reducibility classifies all irreducible level-2 switching methods for cospectral graphs up to size 12.

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

The paper presents two new switching methods that produce cospectral graphs using regular orthogonal matrices of level 2. It also gives combinatorial and geometrical reformulations of prior level-2 operations. By introducing reducibility, the work classifies every irreducible switching method that arises from conjugation by such a matrix with exactly one nontrivial indecomposable block, for all switching sets of size at most 12. This extends earlier classifications and ties into the observation that most cospectral graphs with cospectral complements arise from these matrices. A reader would care because the methods supply explicit constructions and a systematic way to enumerate the basic building blocks of such operations.

Core claim

The authors introduce two new switching methods of level 2 and several reformulations of existing ones. They define reducibility and use it to classify all irreducible switching methods that correspond to a conjugation with a regular orthogonal matrix of level 2 with one nontrivial indecomposable block, up to switching sets of size 12, extending previous results.

What carries the argument

Reducibility, which decomposes switching methods into irreducible components corresponding to regular orthogonal matrices of level 2 having a single nontrivial indecomposable block.

If this is right

  • Two new explicit switching methods become available for constructing pairs of cospectral graphs.
  • All irreducible level-2 switching methods with one nontrivial block are now listed up to size 12.
  • The classification extends earlier enumerations of level-2 operations.
  • Reformulations allow the same switches to be described in combinatorial or geometric terms.

Where Pith is reading between the lines

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

  • The classification supplies a finite list of basic building blocks that any larger reducible switch must be assembled from.
  • Future searches for cospectral graphs beyond size 12 can focus on reducible combinations or matrices with multiple blocks.
  • The combinatorial reformulations may simplify computer-assisted enumeration of cospectral pairs.

Load-bearing premise

Every relevant level-2 switching operation admits a representation by a regular orthogonal matrix whose nontrivial part is a single indecomposable block, and exhaustive enumeration up to size 12 captures all combinatorially distinct irreducible cases.

What would settle it

An explicit irreducible switching method on a set of size 13 whose corresponding orthogonal matrix requires more than one nontrivial indecomposable block, or a duplicate or missing case found in the enumerated list up to size 12.

Figures

Figures reproduced from arXiv: 2410.07948 by Aida Abiad, Nils van de Berg, Robin Simoens.

Figure 1
Figure 1. Figure 1: Cospectral mates, obtained by Six vertex AH-switching. [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Cospectral mates, obtained by Fano switching. [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: Cospectral mates, obtained by Cube switching. [PITH_FULL_IMAGE:figures/full_fig_p025_4.png] view at source ↗
read the original abstract

A switching method is a graph operation that results in cospectral graphs (graphs with the same spectrum). Work by Wang and Xu [Discrete Math. 310 (2010)] suggests that most cospectral graphs with cospectral complements can be constructed using regular orthogonal matrices of level 2, which has relevance for Haemers' conjecture. We present two new switching methods and several combinatorial and geometrical reformulations of existing switching operations of level 2. We also introduce the concept of reducibility and use it to classify all irreducible switching methods that correspond to a conjugation with a regular orthogonal matrix of level 2 with one nontrivial indecomposable block, up to switching sets of size 12, extending previous results.

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

Summary. The manuscript presents two new level-2 switching methods for constructing cospectral graphs, offers combinatorial and geometrical reformulations of prior level-2 operations, introduces the notion of reducibility, and classifies all irreducible switching methods arising from conjugation by a regular orthogonal matrix of level 2 possessing exactly one nontrivial indecomposable block, up to switching-set size 12.

Significance. If the classification is complete and correct, the work extends earlier enumerations of switching methods and supplies explicit constructions that may assist investigations of cospectral graphs and Haemers' conjecture. The reformulations and the reducibility concept provide useful organizational tools. Explicit constructions are a clear strength.

major comments (1)
  1. [classification section] The classification result (the section presenting the enumeration and list of irreducible methods) rests on the claim that the reducibility criterion together with exhaustive search up to size 12 captures every combinatorially distinct case without omissions or duplicates. No independent verification protocol, machine-checked enumeration, or explicit listing of all candidate matrices and partitions is supplied, so an incomplete search criterion would silently truncate the reported list and undermine the completeness assertion.
minor comments (1)
  1. [reformulations section] Notation for the regular orthogonal matrices and the switching sets should be made uniform across the reformulation subsections to avoid ambiguity when comparing the new methods to the earlier Wang-Xu constructions.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed reading and for identifying a point that strengthens the presentation of our classification result. We address the single major comment below.

read point-by-point responses

  1. Referee: [classification section] The classification result (the section presenting the enumeration and list of irreducible methods) rests on the claim that the reducibility criterion together with exhaustive search up to size 12 captures every combinatorially distinct case without omissions or duplicates. No independent verification protocol, machine-checked enumeration, or explicit listing of all candidate matrices and partitions is supplied, so an incomplete search criterion would silently truncate the reported list and undermine the completeness assertion.

    Authors: We agree that the manuscript would benefit from a more explicit account of the search procedure. The classification was obtained by an exhaustive enumeration over all partitions of [n] for n ≤ 12 together with all regular orthogonal matrices of level 2 having exactly one nontrivial indecomposable block; the reducibility criterion was applied to discard reducible cases and to identify duplicates up to combinatorial equivalence. In the revision we will add a dedicated subsection describing the enumeration algorithm, the data structures used for partitions and matrices, and the checks performed to confirm completeness and absence of duplicates within the finite range n ≤ 12. We will also indicate that the implementing code can be made available as supplementary material. These additions directly supply the requested verification protocol without altering the reported list. revision: yes

Circularity Check

0 steps flagged

No circularity; explicit combinatorial constructions and enumeration

full rationale

The paper introduces new switching methods via direct combinatorial and geometrical reformulations, defines reducibility, and performs an enumeration-based classification of irreducible cases up to size 12. No step equates a claimed prediction or result to its own inputs by definition, fitted parameter, or self-citation chain. The classification rests on explicit matrix representations and exhaustive search under the stated criteria, which are independent of the output list. This is self-contained combinatorial work against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definitions of graph spectra, orthogonal matrices, and cospectrality already present in the literature cited by the abstract; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • domain assumption Standard definitions and basic properties of adjacency matrices, eigenvalues, and orthogonal matrices over the reals in spectral graph theory.
    The paper operates entirely inside the established framework of linear algebra applied to graphs.

pith-pipeline@v0.9.0 · 5646 in / 1247 out tokens · 36983 ms · 2026-05-23T18:55:15.826726+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A general switching method for constructing E-cospectral hypergraphs

    math.CO 2026-04 unverdicted novelty 7.0

    A unified switching construction produces E-cospectral uniform hypergraphs and shows that one standard method for computing E-characteristic polynomials is uninformative for almost all hypergraphs.

  2. Almost all graphs have no cospectral mates with height relative small to its order

    math.CO 2026-04 unverdicted novelty 7.0

    Almost all graphs of order n have no cospectral mates with height o((n / ln n)^{1/10}).

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · cited by 2 Pith papers

  1. [1]

    Spectral Characterizations of Graphs

    A. Abiad. “Spectral Characterizations of Graphs”. PhD thesis . Tilburg University, 2015

    work page 2015

  2. [2]

    Con- structions of cospectral graphs with different zero forcing numb ers

    A. Abiad, B. Brimkov, J. Breen, T. R. Cameron, H. Gupta, and R. Villagran. “Con- structions of cospectral graphs with different zero forcing numb ers”. In: Electron. J. Linear Algebra 38 (2022)

    work page 2022

  3. [3]

    Graph switching, 2-ran ks, and graphical Hadamard matrices

    A. Abiad, S. Butler, and W. H. Haemers. “Graph switching, 2-ran ks, and graphical Hadamard matrices”. In: Discrete Math. 342.10 (2019), pp. 2850–2855

    work page 2019

  4. [4]

    Cospe ctral mates for generalized Johnson and Grassmann graphs

    A. Abiad, J. D’haeseleer, W. H. Haemers, and R. Simoens. “Cospe ctral mates for generalized Johnson and Grassmann graphs”. In: Linear Algebra Appl. 678 (2023), pp. 1–15

    work page 2023

  5. [5]

    Cospectral graphs and regular or thogonal matrices of level 2

    A. Abiad and W. H. Haemers. “Cospectral graphs and regular or thogonal matrices of level 2”. In: Electron. J. Comb. (2012), #P13

    work page 2012

  6. [6]

    Switched symplectic graphs and the ir 2-ranks

    A. Abiad and W. H. Haemers. “Switched symplectic graphs and the ir 2-ranks”. In: Des. Codes, Cryptogr. 81 (2016), pp. 35–41

    work page 2016

  7. [7]

    New families of str ongly regular graphs

    S. G. Barwick, W.-A. Jackson, and T. Penttila. “New families of str ongly regular graphs”. In: Australas. J. Comb. 67 (2016), pp. 486–507

    work page 2016

  8. [8]

    Cospectral regula r graphs with and without a perfect matching

    Z. Blazsik, J. Cummings, and W. H. Haemers. “Cospectral regula r graphs with and without a perfect matching”. In: Discrete Math. 338 (2015), pp. 199–201

    work page 2015

  9. [9]

    Cospectral graphs on 12 vertic es

    A. E. Brouwer and E. Spence. “Cospectral graphs on 12 vertic es”. In: Electron. J. Comb. 16 (2009), N20

    work page 2009

  10. [10]

    On inequivalent weig hing matrices

    H. C. Chan, C. A. Rodger, and J. Seberry. “On inequivalent weig hing matrices”. In: Ars Comb. 21.A (1986), pp. 299–333

    work page 1986

  11. [11]

    Developments on spectral c haracterizations of graphs

    E. R. van Dam and W. H. Haemers. “Developments on spectral c haracterizations of graphs”. In: Discrete Math. 309 (2009), pp. 576–586

    work page 2009

  12. [12]

    Which graphs are determined by their spec- trum?

    E. R. van Dam and W. H. Haemers. “Which graphs are determined by their spec- trum?” In: Linear Algebra Appl. 373 (2003), pp. 241–272

    work page 2003

  13. [13]

    A general construction of strictly Neumaier graphs and a related switching

    R. J. Evans, S. Goryainov, E. V. Konstantinova, and A. D. Med nykh. “A general construction of strictly Neumaier graphs and a related switching”. In: Discrete Math. 346 (2023), p. 113384

    work page 2023

  14. [14]

    Constructing cospectral graphs

    C. D. Godsil and B. McKay. “Constructing cospectral graphs ”. In: Aequationes Math. 25.1 (1982), pp. 257–268

    work page 1982

  15. [15]

    Some computational results on the spectra of graphs

    C. D. Godsil and B. Mckay. “Some computational results on the spectra of graphs”. In: Combinatorial Mathematics IV . Ed. by Louis R. A. Casse and Walter D. Wallis. Berlin, Heidelberg: Springer Berlin Heidelberg, 1976, pp. 73–92

    work page 1976

  16. [16]

    Graphs cospectral with Knes er graphs

    W. H. Haemers and F. Ramezani. “Graphs cospectral with Knes er graphs”. In: Graphs Comb. 531 (2009), pp. 159–164

    work page 2009

  17. [17]

    Enumeration of cospectral gr aphs

    W. H. Haemers and E. Spence. “Enumeration of cospectral gr aphs”. In: Eur. J. Comb. 25.2 (2004), pp. 199–211

    work page 2004

  18. [18]

    Circulant weighing matrices

    R. M. Hain. “Circulant weighing matrices”. Master’s thesis. Aust ralian National University, 1977. 26

    work page 1977

  19. [19]

    New strongly regular graphs fr om finite geometries via switching

    F. Ihringer and A. Munemasa. “New strongly regular graphs fr om finite geometries via switching”. In: Linear Algebra Appl. 580 (2019), pp. 464–474

    work page 2019

  20. [20]

    Graphs cospectra l with NU( n + 1, q 2), n ̸= 3

    F. Ihringer, F. Pavese, and V. Smaldore. “Graphs cospectra l with NU( n + 1, q 2), n ̸= 3”. In: Discrete Math. 344 (2021), p. 112560

    work page 2021

  21. [21]

    A note on cospectral graphs

    C. R. Johnson and M. Newman. “A note on cospectral graphs” . In: J. Comb. Theory B 28 (1980), pp. 96–103

    work page 1980

  22. [22]

    Generalized cospectral g raphs with and without Hamiltonian cycles

    F. Liu, W. Wang, T. Yu, and H.-J. Lai. “Generalized cospectral g raphs with and without Hamiltonian cycles”. In: Linear Algebra Appl. 585 (2020), pp. 199–208

    work page 2020

  23. [23]

    Constructing cospectral graphs via regu- lar rational orthogonal matrices with level two

    L. Mao, W. Wang, F. Liu, and L. Qiu. “Constructing cospectral graphs via regu- lar rational orthogonal matrices with level two”. In: Discrete Math. 346.1 (2023), p. 113156

    work page 2023

  24. [24]

    Constructing cospectral graphs via regu lar rational orthogonal matrix with level two and three

    L. Mao and F. Yan. “Constructing cospectral graphs via regu lar rational orthogonal matrix with level two and three”. In: arXiv:2409.09998 (2024)

    work page arXiv 2024

  25. [25]

    Godsil–McKay switching and twisted Grassmann g raphs

    A. Munemasa. “Godsil–McKay switching and twisted Grassmann g raphs”. In: Des. Codes Cryptogr. 84 (2015), pp. 173–179

    work page 2015

  26. [26]

    SageMath, the Sage Mathematics Software System (Version 10.1)

    The Sage Developers. SageMath, the Sage Mathematics Software System (Version 10.1). https://www.sagemath.org

    work page

  27. [27]

    Some results on weighing matrices

    J. S. Wallis and A.L. Whiteman. “Some results on weighing matrices” . In: B. Aust. Math. Soc. 12.3 (1975), pp. 433–447

    work page 1975

  28. [28]

    Cospectral graphs, GM-switching and regular rational orthogonal matrices of level p

    W. Wang, L. Qiu, and Y. Hu. “Cospectral graphs, GM-switching and regular rational orthogonal matrices of level p”. In: Linear Algebra Appl. 563 (2019), pp. 154–177

    work page 2019

  29. [29]

    On the asymptotic behavior of graphs de termined by their generalized spectra

    W. Wang and C.-X. Xu. “On the asymptotic behavior of graphs de termined by their generalized spectra”. In: Discrete Math. 310 (2010), pp. 70–76. 27 A Appendix In this appendix, we describe how to find the irreducible matrices for a given switching method of level 2. The code for this can be found on https://github.com/robinsimoens/level-2-switchi We used t...

    work page 2010

  30. [30]

    patching

    First, we determine all elements of BR. For Fano switching and Cube switching, this is feasible in a straightforward way, by looping through all symmetric 01-matrices B and checking whether RT BR is again a 01-matrix. For the switching methods of the infinite family from Theorem 3(ii), we use equation (3) to first determ ine the possible 4 × 4 submatrices c...

    work page

  31. [31]

    stabiliser

    Since BR is invariant under complementation and under certain conjugations (see Lemma 15), we calculate the “stabiliser” of the matrix R and use it to choose one representative for each conjugacy class of matrices in BR

    work page

  32. [32]

    directed

    Finally, we check which of the remaining matrices are reducible. We fi rst create a list of all orthogonal matrices whose largest indecomposable block is sm aller in size. For Twelve vertex switching, we have to be extra careful that there a re two types of matrices with two indecomposable blocks of size 6, since Six vertex AH-switchin g is “directed”. The...

    work page