{"id":"21955ce5-d642-48ba-b389-91581aee6203","arxiv_id":"1908.02220","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Signed graph analogues of Godsil-McKay and generalized GM-switching are defined and proven to produce cospectral signed graphs.","lead":"This paper adapts two known graph-switching constructions, the Godsil-McKay switching and a generalized version, to signed graphs where edges can be labeled +1 or -1. The result is a recipe for producing different signed graphs that share the same eigenvalues, with worked examples.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The paper's central claims are the two cospectrality theorems for signed graph switching. Both proofs are elementary similarity transformations by rational orthogonal matrices, and the hypotheses are precisely the conditions under which the transformed matrix is again the signed adjacency matrix of the described switched graph. I re-verified the key steps: Lemma 3.1, the Q-matrix action on the column blocks in Theorem 3.2, and the N11, N12 cancellation in Theorem 5.1. The one slightly opaque intermediate line in the N12 computation is not an error once the row/column sum identities from Eq. (2) are applied. The examples are explicit, and the non-switching-isomorphism arguments are valid (degree change in Example 3.3; non-cospectral underlying graphs in Example 5.2). The reader's weakest assumption correctly points to the column-type restrictions, but these are necessary design conditions of the switching routine, not a hidden flaw: if they fail, the construction simply does not produce a signed graph, which is exactly what the theorems condition on. Since no part of the central argument appears incorrect, the ACCEPT verdict stands.","tokens_in":96494,"tokens_out":19546,"duration_ms":182352,"concrete_test":"Independently recompute the conjugation in Theorem 5.1 for Example 5.2 with a symbolic algebra system: enter the displayed 14×14 signed adjacency matrix, form Q = diag(U_10, I_4) with U_10 = I_10 + (1/5)[[-J_5, J_5],[J_5, -J_5]], compute QAQ, and verify that every entry is in {-1,0,1}, the matrix is symmetric, and its characteristic polynomial equals the stated p_Γ(x) = x^14 - 46x^12 + 770x^10 - 22x^9 - ... - 489.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking both central constructions, I find no load-bearing flaw in the argument. Theorem 3.2 is a direct matrix-conjugation proof: the five column conditions in Lemma 3.1 are exactly the cases in which Q_m maps a (-1,0,1)-vector to another (-1,0,1)-vector, and the row/column sum assumptions on C_i and C_ij make the conjugation leave those blocks unchanged. The switching rules match the Q_m action in each case, including the d±=0 case where Q_m x = -x is a sign change. Theorem 5.1 likewise checks out: the condition d±_1(v)-d±_2(v)=d±_2(u)-d±_1(u)=ℓ gives exactly Eq. (2), and the N11, N12 algebra reduces to 0 once one uses the identities (A1-B)J = ℓJ, J(A1-B^T) = ℓJ, J(A2-B^T)J = mℓJ, and the equivalent column-sum identities. The displayed intermediate N12 expression has a compressed step, but the final cancellation is valid. The column-type restrictions are genuinely the conditions that keep the conjugated matrix inside the class of signed adjacency matrices, and the examples satisfy them; this is a scope condition, not a gap. The non-switching-isomorphism claims in Examples 3.3 and 5.2 are justified by degree reasons or by non-cospectrality of the underlying unsigned graphs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":96735,"tokens_out":19668,"duration_ms":187716,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 3, switching definition before Theorem 3.2"},{"comment":"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.","section":"Section 5, switching definition before Theorem 5.1"},{"comment":"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.","section":"Theorem 5.1 proof, N12 computation"},{"comment":"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'.","section":"Abstract and Introduction"},{"comment":"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.","section":"Example 3.3"},{"comment":"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.","section":"Remarks 3.5 and 5.3"}],"recommendation":"minor_revision","confidential_remarks":"The paper is mathematically sound. The only substantive issues are definitional: in both switching constructions, the prose omits the explicit 'no change' behavior for some of the allowed cases, although the proofs clearly imply it. These are easy to fix with one added sentence per theorem. The algebra in Theorem 5.1 is correct but slightly compressed. The paper is incremental but appropriate for the journal, and I see no citation or novelty concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a correct and genuinely new extension of Godsil–McKay switching and the Wang–Qiu–Hu generalized switching to signed graphs. Anyone working on cospectral signed graphs or spectral characterizations will want this in the toolbox. I checked the algebra in Section 5 and the stress-test note is right: the N11/N12 cancellation goes through once you use the sum identities; the displayed N12 step is compressed but valid.\n\nWhat's actually new: the signed GM-switching (Theorem 3.2) and signed G-GM-switching (Theorem 5.1), with net-degree conditions replacing degree conditions. The five column conditions in Lemma 3.1 are exactly the cases where Q_m preserves the signed adjacency structure. The unsigned theorems come out as special cases, which is good. The examples are explicit and the characteristic polynomials are given, so a reader can verify without redoing the proof.\n\nSoft spots, mostly minor. The hypotheses are genuinely restrictive—every vertex in the switching set must meet one of the column-type conditions, and the constant net-degree difference ℓ must hold exactly. That's not a flaw; it's the price of the construction, and the paper doesn't overclaim applicability. One wording issue: the abstract says 'we can build pairs of cospectral switching nonisomorphic signed graphs,' which could be read as a general statement that the construction always yields non-isomorphic pairs. What's proven is cospectrality; non-switching-isomorphism is demonstrated in the examples. A careful referee might ask the authors to soften the abstract or state the examples explicitly. Also, the paper doesn't discuss whether the signed switching produces pairs that are new in any deeper sense—e.g., not just signed-permutation conjugates—but the examples already show that.\n\nThe citation pattern looks right: unsigned predecessors [9,12] are credited, and I don't see a missing signed version. The proofs are self-contained matrix conjugations. No circularity.\n\nWho is this for: spectral graph theorists, especially people interested in signed graphs and cospectrality. It's a solid subfield contribution, not a breakthrough, but it's clearly correct and useful. I'd send it out for review without hesitation. I'd probably not cite it in my own next project unless I work on signed graph constructions, but it's a fair reference.","headline":"Correct and genuinely new signed-graph extensions of GM-switching; the hypotheses are restrictive but the matrix proofs are explicit and the examples hold.","tokens_in":97257,"tokens_out":3027,"would_cite":true,"duration_ms":32443,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C22","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves two switching routines that create pairs of cospectral, non-isomorphic signed graphs.","keywords":["signed graphs","cospectral graphs","Godsil-McKay switching","generalized Godsil-McKay switching","adjacency spectrum","signature switching","switching isomorphism","PINGS"],"falsifier":"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.","tokens_in":96311,"feed_emoji":"🔀","tokens_out":8520,"duration_ms":94894,"temperature":0.7,"pith_summary":"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.","feed_headline":"Two routines now make non-isomorphic signed graphs cospectral","feed_subtitle":"Adapted Godsil-McKay switching gives every eligible signed graph a cospectral, non-isomorphic twin.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It supplies the original Godsil-McKay switching and the Q-matrix proof that Section 3 adapts to signed entries.","marker":"[9]"},{"why":"It provides the generalized GM-switching with the $U_{2p}$ matrix that Section 5 extends to signed graphs and to any block size $m$.","marker":"[12]"},{"why":"It establishes the signed-graph framework of switching equivalence and balance that the paper builds upon.","marker":"[13]"},{"why":"It sets the spectral theory of signed graphs and the open problems that make cospectral signed pairs worth constructing.","marker":"[2]"},{"why":"It states the $(0,1)$-matrix variant of GM-switching that becomes Proposition 3.4 after allowing $-1$ entries.","marker":"[10]"},{"why":"It provides the historical starting point for routines that construct non-isomorphic cospectral graphs.","marker":"[11]"}],"fun_headline_variants":["Godsil-McKay switching now yields cospectral signed graph twins","Signed graphs get cospectral non-isomorphic pairs via GM switching","Adapted GM switching constructs cospectral signed graph pairs","Switching makes signed graphs cospectral and non-isomorphic"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Godsil-McKay switching now yields cospectral signed graph twins","Signed graphs get cospectral non-isomorphic pairs via GM switching","Adapted GM switching constructs cospectral signed graph pairs","Switching makes signed graphs cospectral and non-isomorphic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00072,"raw_usage":{"total_tokens":3206,"prompt_tokens":893,"completion_tokens":2313,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":509,"completion_tokens_details":{"reasoning_tokens":2244}},"tokens_in":509,"tokens_out":2313,"duration_ms":17526,"temperature":1.0,"reasoning_tokens":2244,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:50:05.972607+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Godsil, B","cited_arxiv_id":null,"evidence_quote":"It supplies the original Godsil-McKay switching and the Q-matrix proof that Section 3 adapts to signed entries."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It provides the generalized GM-switching with the $U_{2p}$ matrix that Section 5 extends to signed graphs and to any block size $m$."},{"cited_title":"Belardo, S","cited_arxiv_id":null,"evidence_quote":"It sets the spectral theory of signed graphs and the open problems that make cospectral signed pairs worth constructing."},{"cited_title":"Haemers, E","cited_arxiv_id":null,"evidence_quote":"It states the $(0,1)$-matrix variant of GM-switching that becomes Proposition 3.4 after allowing $-1$ entries."},{"cited_title":"Schwenk, Almost All Trees Are Cospectral, in: Hara ry, F., Ed., New Directions in the Theory of Graphs , Academic Press, New York, 275-307","cited_arxiv_id":null,"evidence_quote":"It provides the historical starting point for routines that construct non-isomorphic cospectral graphs."}],"review_version":1}