Edge perturbation on signed graphs with clusters: Adjacency and Laplacian eigenvalues

Let Γ = (G, σ_Γ ) be a signed graph, where G is the underlying simple graph and σ_Γ: E(G→{+1,−1} is the sign function on the edges of G. A (c, s)-cluster in Γ is a pair of vertex subsets (C, S), where C is a set of cardinality |C| = c ≥ 2 of pairwise co-neighbour vertices sharing the same set S of s neighbours. For each signed graph Λ of order c we consider the graph Γ (Λ) obtained by adding the edges of Λ, after suitably identifying C and V(Λ). It turns out that Γ (Λ) and Γ (Λ′) share part of their adjacency (resp. Laplacian) spectrum if Λ and Λ′ both show the sign-based regularity known as net-regularity (resp. negative regularity). Our results offer a generalization to signed graph of some theorems by Domingos Cardoso and Oscar Rojo concerning edge perturbations on (unsigned) graphs with clusters.