Index perturbation of signed graphs

Linfeng Xie; Xiaogang Liu

arxiv: 2606.10783 · v1 · pith:LWNZ64RTnew · submitted 2026-06-09 · 🧮 math.CO

Index perturbation of signed graphs

Linfeng Xie , Xiaogang Liu This is my paper

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

classification 🧮 math.CO

keywords signed graphslargest eigenvaluevertex deletionspectral boundswitching equivalencebalanced signed graphsadjacency matrix

0 comments

The pith

The largest eigenvalue of a signed graph is bounded above by the square root of the deleted graph's eigenvalue squared plus twice the vertex degree minus one.

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

This paper proves that for a signed graph Γ and non-isolated vertex v, the largest eigenvalue satisfies λ₁(Γ) ≤ √[λ₁²(Γ − v) + 2d_Γ(v) − 1]. A refined version of the bound is also derived. Equality cases are characterized for connected graphs with degree at least two as those switching-equivalent to the balanced complete signed graph. The result describes how the spectrum changes when a vertex is removed while preserving the signed edge structure.

Core claim

The paper shows that the largest eigenvalue λ₁(Γ) of a signed graph Γ satisfies λ₁(Γ) ≤ √[λ₁²(Γ − v) + 2d_Γ(v) − 1] for a non-isolated vertex v. It presents a refined version of this bound and characterizes the extremal signed graphs achieving equality when Γ is connected and d_Γ(v) ≥ 2, which are switching equivalent to the balanced complete signed graph.

What carries the argument

The symmetric adjacency matrix of the signed graph with entries in {-1,0,1}, whose spectral radius is the largest eigenvalue, used to bound the change upon deletion of a row and column corresponding to vertex v.

Load-bearing premise

The largest eigenvalue of the signed graph is the spectral radius of its symmetric adjacency matrix, and deleting a vertex removes the corresponding row and column while preserving all signed edges.

What would settle it

Compute the eigenvalues of any connected signed graph with a vertex v of degree at least two; if λ₁(Γ) exceeds √[λ₁²(Γ − v) + 2d_Γ(v) − 1] for that graph, the bound is false.

read the original abstract

Let $\Gamma = (G, \sigma)$ be a signed graph and $v$ a non-isolated vertex of $\Gamma$. Let $\Gamma-v$ denote the graph obtained by deleting the vertex $v$ together with all signed edges incident to it from $\Gamma$, and $d_{\Gamma}(v)$ the degree of $v$ in $\Gamma$. In this paper, we prove that the largest eigenvalue $\lambda_1(\Gamma)$ of $\Gamma$ satisfies \[ \lambda_1(\Gamma) \le \sqrt{\lambda_1^2(\Gamma - v) + 2d_\Gamma(v) - 1}, \] and we also present a refined version of this bound. Moreover, we characterize the extremal signed graphs achieving equality when $\Gamma$ is connected and $d_\Gamma(v)\ge 2$, which are switching equivalent to the balanced complete signed graph.

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.

Desk Editor's Note private letter to a colleague

This paper gives a consistent perturbation bound on the largest eigenvalue of signed graphs after vertex deletion, with equality when switching-equivalent to the balanced complete case.

read the letter

The main point is a clean upper bound λ1(Γ) ≤ sqrt(λ1(Γ−v)^2 + 2dΓ(v)−1) for signed graphs, plus a characterization that equality holds precisely when the graph is switching-equivalent to the balanced complete signed graph (for connected cases with d(v)≥2).

The work applies standard matrix perturbation ideas to the signed setting and pins down the equality case using the known spectrum of the balanced Kn. The stress-test confirms the inequality is internally consistent with the symmetric adjacency matrix having entries in {-1,0,1} and reduces correctly on the extremal example. That is useful for anyone needing explicit recursive estimates in this area.

The bound and the switching-equivalence handling are the concrete contributions. A refined version is mentioned but not detailed in the abstract.

The limitation is that this remains an incremental refinement rather than a new technique or broader framework. The abstract alone does not show the derivation steps, so a referee would need to verify the matrix identities and the handling of signed edges, but no circularity or load-bearing gaps appear from the given information.

This is for specialists in spectral graph theory who work with signed graphs. A reader already following eigenvalue bounds in that subfield would get a usable estimate and equality cases from it.

I would send it to peer review. The claim is well-posed, the math lines up on the surface, and it adds a precise, falsifiable result even if the scope is narrow.

Referee Report

0 major / 1 minor

Summary. The paper proves that for a signed graph Γ = (G, σ) and non-isolated vertex v, the largest eigenvalue satisfies λ₁(Γ) ≤ √[λ₁²(Γ − v) + 2d_Γ(v) − 1], presents a refined version of the bound, and characterizes equality cases (when Γ is connected and d_Γ(v) ≥ 2) as the graphs switching-equivalent to the balanced complete signed graph.

Significance. If the derivation holds, the result supplies a concrete perturbation bound on the spectral radius of signed graphs that reduces exactly to the known spectrum of the balanced complete signed graph in the equality case. This extends classical index bounds from unsigned graphs and supplies a sharp extremal characterization in terms of switching equivalence.

minor comments (1)

[Abstract] Abstract: the refined version of the bound is announced but not displayed; stating the refined inequality explicitly would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive evaluation and recommendation of minor revision. The report accurately summarizes the main result and its significance. Since no specific major comments are raised, we will proceed with any minor editorial adjustments suggested by the editor or production.

Circularity Check

0 steps flagged

No significant circularity; bound is a direct matrix inequality

full rationale

The claimed inequality λ₁(Γ) ≤ √[λ₁²(Γ−v) + 2d_Γ(v)−1] is presented as a perturbation bound on the spectral radius of the symmetric adjacency matrix of the signed graph. Vertex deletion produces the corresponding principal submatrix, and the bound follows from standard quadratic-form or interlacing arguments on symmetric matrices with entries in {-1,0,1}. The equality characterization for connected graphs with d(v)≥2 reduces exactly to the known spectrum of the balanced complete signed graph (λ₁ = n−1), which is an external, independently verifiable fact rather than a self-referential fit. No self-definitional step, fitted-input prediction, load-bearing self-citation, or ansatz smuggling appears in the derivation chain. The result is self-contained against external matrix theory benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard definition of the signed adjacency matrix and the fact that switching equivalence preserves the spectrum; no free parameters or new entities are introduced.

axioms (2)

standard math The adjacency matrix of a signed graph is real symmetric with entries in {-1,0,1}, hence has real eigenvalues and a well-defined largest eigenvalue λ₁.
Used to define λ₁(Γ) and to justify that vertex deletion produces a principal submatrix.
domain assumption Switching equivalence (sign flips around a vertex subset) leaves the spectrum of the signed graph invariant.
Invoked in the characterization of extremal graphs achieving equality.

pith-pipeline@v0.9.1-grok · 5679 in / 1367 out tokens · 21222 ms · 2026-06-27T12:47:13.287910+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references

[1]

P. J. Cameron, J. J. Seidel, S. V. Tsaranov, Signed graphs, root lattices, and Coxeter groups, J. Algebra 164 (1) (1994) 173–209

1994
[2]

D. M. Cvetkovi´ c, M. Doob, H. Sachs, Spectra of Graphs, Academic Press, New York, 1980

1980
[3]

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

2010
[4]

Harary, On the notion of balance of a signed graph, Michigan Math

F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (2) (1953) 143–146

1953
[5]

Heider, Attitudes and cognitive organization, J

F. Heider, Attitudes and cognitive organization, J. Psychol. 21 (1) (1946) 107–112

1946
[6]

Guo, Z.-W

J.-M. Guo, Z.-W. Wang, X. Li, Sharp upper bounds of the spectral radius of a graph, Discrete Math. 342 (2019) 2559–2563

2019
[7]

L. Liu, B. Ning, A short proof of an inequality on spectral radius perturbation, arXiv:2603.29335 (2026)

arXiv 2026
[8]

S. Sun, K. C. Das, A conjecture on the spectral radius of graphs, Linear Algebra Appl. 588 (2020) 74–80

2020
[9]

Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl

V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl. 432 (9) (2010) 2243–2256

2010
[10]

Zaslavsky, Signed graphs, Discrete Appl

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

1982
[11]

Zaslavsky, Matrices in the theory of signed simple graphs, in Advances in Discrete Mathematics and Applications: Mysore, 2008, 207–229, Ramanujan Math

T. Zaslavsky, Matrices in the theory of signed simple graphs, in Advances in Discrete Mathematics and Applications: Mysore, 2008, 207–229, Ramanujan Math. Soc. Lect. Notes Ser., 13, Ramanujan Math. Soc., Mysore, 2010

2008
[12]

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

T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, Electron. J. Combin. 5 (2018), Dynamic Surveys 8, 524 pages. 5

2018

[1] [1]

P. J. Cameron, J. J. Seidel, S. V. Tsaranov, Signed graphs, root lattices, and Coxeter groups, J. Algebra 164 (1) (1994) 173–209

1994

[2] [2]

D. M. Cvetkovi´ c, M. Doob, H. Sachs, Spectra of Graphs, Academic Press, New York, 1980

1980

[3] [3]

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

2010

[4] [4]

Harary, On the notion of balance of a signed graph, Michigan Math

F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (2) (1953) 143–146

1953

[5] [5]

Heider, Attitudes and cognitive organization, J

F. Heider, Attitudes and cognitive organization, J. Psychol. 21 (1) (1946) 107–112

1946

[6] [6]

Guo, Z.-W

J.-M. Guo, Z.-W. Wang, X. Li, Sharp upper bounds of the spectral radius of a graph, Discrete Math. 342 (2019) 2559–2563

2019

[7] [7]

L. Liu, B. Ning, A short proof of an inequality on spectral radius perturbation, arXiv:2603.29335 (2026)

arXiv 2026

[8] [8]

S. Sun, K. C. Das, A conjecture on the spectral radius of graphs, Linear Algebra Appl. 588 (2020) 74–80

2020

[9] [9]

Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl

V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl. 432 (9) (2010) 2243–2256

2010

[10] [10]

Zaslavsky, Signed graphs, Discrete Appl

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

1982

[11] [11]

Zaslavsky, Matrices in the theory of signed simple graphs, in Advances in Discrete Mathematics and Applications: Mysore, 2008, 207–229, Ramanujan Math

T. Zaslavsky, Matrices in the theory of signed simple graphs, in Advances in Discrete Mathematics and Applications: Mysore, 2008, 207–229, Ramanujan Math. Soc. Lect. Notes Ser., 13, Ramanujan Math. Soc., Mysore, 2010

2008

[12] [12]

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

T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, Electron. J. Combin. 5 (2018), Dynamic Surveys 8, 524 pages. 5

2018