Pith. sign in

REVIEW 6 minor 15 references

Constructing cospectral signed graphs

T0 review · 0 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves two switching routines that create pairs of cospectral, non-isomorphic signed graphs.

desk verdict Correct and genuinely new signed-graph extensions of GM-switching; the hypotheses are restrictive but the matrix proofs are explicit and the examples hold. read the letter →

arxiv 1908.02220 v1 pith:5TPZFIOC submitted 2019-08-06 math.CO

Francesco Belardo , Maurizio Brunetti , Matteo Cavaleri , Alfredo Donno This is my paper · ORCID
classification math.CO MSC 05C2205C50
keywords signedgraphscospectralGodsil-McKayswitchinggeneralizedadjacencyspectrumsignatureisomorphismPINGS
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

Two classical routines for manufacturing pairs of non-isomorphic graphs with identical adjacency spectra, the Godsil-McKay switching and a generalized version, are shown to work for signed graphs whose edges carry plus or minus one. The paper proves that under precise local regularity conditions on each switched vertex, conjugating the signed adjacency matrix by a rational orthogonal matrix produces the adjacency matrix of a genuinely different signed graph with the same spectrum. In the examples the two signed graphs are not switching isomorphic, and even their underlying unsigned graphs are not cospectral, so the shared spectrum is a genuinely signed phenomenon. This supplies spectral graph theory with a systematic way to build cospectral switching nonisomorphic signed graphs, the signed analogue of the classical PINGS.

What carries the argument

The carrier of the argument is the rational orthogonal involution $Q_m=\frac{2}{m}J_m-I_m$, the same matrix used in the classical Godsil-McKay construction. It is symmetric, orthogonal, and satisfies the Q-properties: squaring to the identity, fixing matrices with constant row and column sums, and turning a half-zero, half-one vector into its complement. Lemma 3.1 extends these actions to signed vectors: a zero-sum vector is sent to its negative, a half-plus, half-zero vector to its signed complement, a half-minus, half-zero vector to its negative signed complement, and all-plus or all-minus vectors are fixed. Block-diagonal conjugation by $Q$ applies exactly one of these transformations to each column of the switching blocks, producing the local switching rule, while the constant-sum conditions leave the diagonal blocks unchanged; similarity then forces cospectrality. The generalized switching uses $U_{2m}=I_{2m}+\frac{1}{m}\begin{pmatrix}-J_m & J_m\\ J_m & -J_m\end{pmatrix}$, which swaps the all-plus and all-minus column types and preserves columns with equal net-degree between $V_1$ and $V_2$.

What would settle it

Compute $Q_4 x$ for a column $x=(1,1,-1,0)$ whose entries sum to $1$; the result contains $3/2$ and $-1/2$, values outside $\{-1,0,1\}$. The same calculation shows that each of the five listed column patterns is exactly what keeps the conjugated matrix inside the class of signed adjacency matrices, so any signed graph whose switching columns violate these patterns escapes this particular construction and would require a different argument for cospectrality.

Watch

Extended reading notes

Core claim

The central claim is that the Godsil-McKay switching and the generalized Godsil-McKay switching both carry over to signed graphs. For a signed graph with vertex partition $\{C_1,\dots,C_t,D\}$, if each off-diagonal block column is one of five signed patterns, then conjugating the adjacency matrix by $Q=\operatorname{diag}(Q_{n_1},\dots,Q_{n_t},I_d)$, where $Q_m=\frac{2}{m}J_m-I_m$, gives the adjacency matrix of a locally switched signed graph $\Gamma^\pi$; since $Q$ is orthogonal, $\Gamma$ and $\Gamma^\pi$ have the same characteristic polynomial. The second construction uses a block matrix $U_{2m}$ acting on two equal-size parts $V_1,V_2$ and a net-degree difference condition, and again produces cospectral signed graphs $\Gamma$ and $\Gamma'$. In the all-positive signature both theorems reduce to the known unsigned switching theorems, so the signed version genuinely extends them rather than merely mimicking them.

Load-bearing premise

For the switching to work, every vertex being switched must attach to each block in one of five very regular ways: zero net-degree, all positive, all negative, half positive, or half negative; if a column mixes signs in any other proportion, the conjugated matrix stops being a signed adjacency matrix.

Editorial extensions

If this is right

  • Every signed graph admitting a partition that satisfies Theorem 3.2 or Theorem 5.1 has a cospectral partner produced by an explicit local switching of its edge signs.
  • The signed switching constructions contain the classical unsigned switching as the special case where every edge is positive, so they are strictly broader tools for generating cospectral pairs.
  • Because the conjugating matrices are rational orthogonal but not signed permutation matrices, the resulting pairs are not merely switching equivalent, and in the paper's examples they are non-isomorphic as signed graphs.
  • Any signed graph whose vertex set contains one of the required partitions is certified not to be determined by its adjacency spectrum, giving a practical obstruction to spectral determination.
  • The generalized switching works for equal-size parts of any positive size $m$, since the matrix proof does not require the odd-prime condition used in the unsigned source.

Reading between the lines

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

  • The same matrix recipe suggests a search programme: any rational orthogonal matrix whose conjugation sends signed adjacency matrices to signed adjacency matrices while fixing constant-sum blocks will generate new cospectral pairs, with $Q_m$ and $U_{2m}$ as the first two instances.
  • The local regularity conditions in Theorem 3.2 can be read as a signed analogue of an equitable partition, which may connect this construction to algorithmic uses of equitable partitions for signed graph isomorphism and spectral computation.
  • A natural testable extension is to iterate the switching on the partner graph and ask whether the process stabilises after finitely many steps or produces longer cosmic cycles of cospectral signed graphs.
  • The five-case restriction marks the boundary of this particular routine, but the paper's examples show that the phenomenon of cospectral signed graphs whose underlying unsigned graphs are not cospectral is not an artifact of that restriction.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 6 minor

Summary. The paper adapts two known switching constructions for unsigned graphs to signed graphs. In Section 3 it defines a Godsil-McKay-type local switching for signed graphs, using the rational orthogonal matrix Q_n = (2/n)J_n - I_n, and proves (Theorem 3.2) that if a signed graph admits a partition satisfying the stated net-degree conditions, then the locally switched signed graph is cospectral with the original. In Section 5 it adapts the generalized GM-switching of Wang, Qiu and Hu to signed graphs, using the matrix U_{2m} = I_{2m} + (1/m)[[-J_m,J_m],[J_m,-J_m]], proving the analogous cospectrality statement (Theorem 5.1). The paper gives two worked examples of cospectral, switching-nonisomorphic signed graphs and shows that the unsigned theorems are recovered as special cases.

Significance. The results are correct and provide a useful extension of two established cospectral-graph constructions to the signed-graph setting. The proofs are explicit and self-contained matrix conjugations, and the hypotheses are transparently the exact conditions needed to keep the conjugated matrix inside the class of signed adjacency matrices. The examples are concrete and the non-switching-isomorphism claims are justified by degree or underlying-spectrum arguments. The paper also recovers the classical Godsil-McKay theorem and the Wang-Qiu-Hu theorem as special cases, which makes the contribution easy to evaluate. The novelty is incremental but the paper is a solid contribution to the spectral theory of signed graphs.

minor comments (6)
  1. [Section 3, switching definition before Theorem 3.2] The definition of the locally switched graph Γ^π lists operations only for the cases d±_i(v)=0, d+_i(v)=n_i/2 with d-_i(v)=0, and d-_i(v)=n_i/2 with d+_i(v)=0. The two allowed cases d+_i(v)=n_i and d-_i(v)=n_i are omitted from the construction; the proof shows that in these cases no change occurs, so the definition should state explicitly that the edges between v and C_i are left unchanged.
  2. [Section 5, switching definition before Theorem 5.1] The construction of Γ′ lists operations for the all-positive-to-V1, all-negative-to-V1, and d+_1(v)=d-_2(v)=m cases, but it does not state what happens in the allowed case d±_1(v)=d±_2(v). The proof shows that U_{2m} leaves such columns unchanged, so the definition should add that in this case no edge modification is made.
  3. [Theorem 5.1 proof, N12 computation] The displayed rearrangement of N12 is not a direct algebraic factorization: going from the first line to the second silently replaces J_mBJ_m with J_mB^T J_m (and analogously in the N11 computation). This is valid because J_mBJ_m = J_mB^T J_m, but one intermediate line should be included to make the algebra transparent.
  4. [Abstract and Introduction] There are several typographical errors: in the abstract, 'we can built pairs' should be 'we can build pairs'; in the Introduction, 'egdes' should be 'edges'; in Section 5 the phrase 'possibility of a graph of admitting' should be 'possibility of a graph admitting'.
  5. [Example 3.3] The non-switching-isomorphism argument is terse: it says vertex 5 has degree two in Γ^π but no vertex has degree two in Γ. Giving the full degree sequence of Γ (and of Γ^π) would make the verification immediate and self-contained.
  6. [Remarks 3.5 and 5.3] In the discussion of how the signed theorems reduce to the unsigned ones, it would be helpful to note explicitly that the cases involving negative degrees (d-_i = n_i/2 or d-_i = n_i in Theorem 3.2, and d+_1=d-_2=m in Theorem 5.1) simply do not occur when the signature is all-positive.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central cospectrality results are proven from scratch by explicit orthogonal similarity of adjacency matrices.

full rationale

The central claims, Theorem 3.2 and Theorem 5.1, are self-contained matrix-conjugation proofs rather than renamings or fitted predictions. In Theorem 3.2, Lemma 3.1 is proved in the paper, the five column conditions are exactly the cases where Q_m sends a (-1,0,1)-entry column to another such column, and the constant row/column sum assumptions make the C_i and C_ij blocks invariant under conjugation; the proof then verifies directly that Q A_Gamma Q is the adjacency matrix of the graph Gamma^pi defined by the stated switching rules. The cospectrality of Gamma and Gamma^pi is a genuine consequence of Q^2 = I and similarity, not an input. Similarly, Theorem 5.1 verifies by explicit computation that U_{2m} M U_{2m} = M using equation (2), and that U_{2m} C transforms each allowed column type exactly according to the switching rules, so Q A_Gamma Q is again the adjacency matrix of the constructed graph. The cited results, Godsil-McKay [9] and Wang-Qiu-Hu [12], are external and independent, and the paper actually recovers them as special cases rather than assuming their conclusions. The only self-citation touching the text is reference [2], an open-problems survey by one of the authors, and it is used only as background for signed spectral theory, not load-bearing for either construction. The strict local-regularity hypotheses are scope conditions that keep the conjugated matrix inside the class of signed adjacency matrices; a failure of those hypotheses would simply mean the construction is not applicable, not that a prediction was fitted. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' own prior work, and no ansatz is smuggled in by self-citation. The non-switching-isomorphism claims are justified by independent degree arguments and by non-cospectrality of underlying unsigned graphs, neither of which borrows from the construction's conclusion.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The paper introduces no free parameters, no new axioms beyond standard linear algebra and signed graph definitions, and no invented entities. The only variable is the integer ell in Theorem 5.1, which is not fitted but is a condition satisfied by the graph.

assumptions (2)
  • standard math Matrices that are similar have the same characteristic polynomial.
    Used in the proofs of Theorems 3.2 and 5.1 to conclude cospectrality from Q A Q = A'.
  • domain assumption Signed graph adjacency matrix A_Gamma is a symmetric (-1,0,1)-matrix with zero diagonal, and signature switching corresponds to conjugation by a sign matrix.
    Background from Zaslavsky's theory of signed graphs, used throughout Sections 3 and 5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Constructing cospectral signed graphs." pith.science (2026). https://pith.science/paper/5TPZFIOC

@misc{pith2026190802220,
  author       = {Pith},
  title        = {Pith review of: Constructing cospectral signed graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5TPZFIOC}},
  note         = {Machine review of arXiv:1908.02220}
}
abstract

A well--known fact in Spectral Graph Theory is the existence of pairs of isospectral nonisomorphic graphs (known as PINGS). The work of A.J. Schwenk (in 1973) and of C. Godsil and B. McKay (in 1982) shed some light on the explanation of the presence of isospectral graphs, and they gave routines to construct PINGS. Here, we consider the Godsil-McKay--type routines developed for graphs, whose adjacency matrices are $(0,1)$-matrices, to the level of signed graphs, whose adjacency matrices allow the presence of $-1$'s. We show that, with suitable adaption, such routines can be successfully ported to signed graphs, and we can build pairs of cospectral switching nonisomorphic signed graphs.

Figures

Figures reproduced from arXiv: 1908.02220 by the authors.

Figure 1
Figure 1. The graphs G and Gπ of Example 2.3. Remark 2.4. The idea of the GM-switching is related to the notion of “equitable partition” of the vertex set of a graph. Equitable partitions have a number of significant applications in Graph theory: for example, the vertex set partition of a graph under the action of a group of automorphisms is always equitable. This fact has been used in the context of graph isomorphism algorit… view at source ↗
Figure 2
Figure 2. The graphs Γ and Γπ of Example 3.3. Proposition 3.4. Let N be a (−1, 0, 1)-matrix of order b × c whose column n j may be such that: • either Pb h=1 n j h = 0; • or b/2 entries of n j are equal to 1 and b/2 entries of n j are equal to 0; • or b/2 entries of n j are equal to −1 and b/2 entries of n j are equal to 0; • or n j = 1b; • or n j = −1b. Define N˜ to be the matrix obtained from N by replacing each column n j … view at source ↗
Figure 3
Figure 3. The graphs G and G′ of Example 4.3. 5. The G-GM-switching for signed graphs In the paper [12] the condition that p is an odd prime is used in order to prove some results concerning the possibility of a graph of admitting a G-GM-switching. However, the matrix machinery still works whenever the size of the parts V1 and V2 is any positive integer m. In this section, we extend the G-GM-switching construction to the more… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The graphs Γ and Γ′ of Example 5.2. AΓ =   0 1 0 0 −1 0 1 0 1 −1 1 0 −1 −1 1 0 0 0 0 1 0 1 0 0 1 0 −1 −1 0 0 0 −1 −1 0 0 0 0 −1 1 −1 0 −1 0 0 −1 0 0 0 1 0 −1 0 1 0 1 −1 −1 0 −1 0 0 0 0 −1 0 0 1 1 0 −1 0 1 0 0 0 0 1 0 0 −1 0 0 1 1 1 0 0 1 0 1 0 0…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 14 canonical work pages

  1. [1]

    Abiad, S

    A. Abiad, S. Butler, W.H. Haemers, Graph switching, 2–ra nks, and graphical Hadamard matrices, Discrete Math. (2018), in press, doi:10.1016/j.disc.2018.11.022

    work page doi:10.1016/j.disc.2018.11.022 2018

  2. [2]

    Belardo, S

    F. Belardo, S. Cioaba, J. Koolen, J.F. Wang, Open problem s in the spectral theory of signed graphs, The Art of Discrete and Applied Mathematics 1 (2018) #P2.10

    work page 2018

  3. [3]

    Brouwer, W.H

    A.E. Brouwer, W.H. Haemers, Spectra of Graphs , Springer, New York, 2012

    work page 2012

  4. [4]

    Cvetkovi´ c, M

    D. Cvetkovi´ c, M. Doob, H. Sachs, Spectra of Graphs - Theory and Applications , 3rd Edition, Johan Ambrosius Bart. Verlag, Heidelberg - Leipzig, 1995

    work page 1995

  5. [5]

    Cvetkovi´ c, P

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

    work page 2010

  6. [6]

    Godsil, Algebraic Graph Theory , Graduate Texts in Mathematics 207, Springer-Verlag, New Y ork, 2001

    C. Godsil, Algebraic Graph Theory , Graduate Texts in Mathematics 207, Springer-Verlag, New Y ork, 2001. xx + 439 pp

    work page 2001

  7. [7]

    Godsil, Compact graphs and equitable partitions, Linear Algebra Appl

    C.D. Godsil, Compact graphs and equitable partitions, Linear Algebra Appl. 255 (1997), 259–266

    work page 1997

  8. [8]

    Godsil, B.D

    C.D. Godsil, B.D. McKay, Feasibility conditions for the existence of walk-regular graphs, Linear Algebra Appl. 30 (1980), 51–61

    work page 1980

Show all 15 references
  1. [9]

    Godsil, B

    C.D. Godsil, B. McKay, Constructing cospectral graphs, Aequationes Math. 25 (1982), 257–268

    1982

  2. [10]

    Haemers, E

    W.H. Haemers, E. Spence, Enumeration of Cospectral Gra phs, European J. Combin. 25 (2004) 199–211

    2004

  3. [11]

    Schwenk, Almost All Trees Are Cospectral, in: Hara ry, F., Ed., New Directions in the Theory of Graphs , Academic Press, New York, 275-307

    A.J. Schwenk, Almost All Trees Are Cospectral, in: Hara ry, F., Ed., New Directions in the Theory of Graphs , Academic Press, New York, 275-307

  4. [12]

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

    2019

  5. [13]

    Zaslavsky, Signed graphs, Discrete Appl

    T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982) 47–74

    1982

  6. [14]

    Zaslavsky, Matrices in the theory of signed simple gr aphs, Advances in Discrete Mathematics and Applications: Mysore, 2008, Ramanujan Math

    T. Zaslavsky, Matrices in the theory of signed simple gr aphs, Advances in Discrete Mathematics and Applications: Mysore, 2008, Ramanujan Math. Soc., Mysore, 2010, pp. 207–2 29

    2008

  7. [15]

    Zaslavsky, A mathematical bibliography of signed an d gain graphs and allied areas, Electron

    T. Zaslavsky, A mathematical bibliography of signed an d gain graphs and allied areas, Electron. J. Combin., Dynamic Surveys DS8, URL: http://www.combinatorics.org/ojs/ind ex.php/eljc/article/view/DS8/pdf. Francesco Belardo, Universit `a degli Studi di Napoli Federico II, Via ...

Pith tools

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