Let Γ=(G,σ)Γ=(G,σ) be a connected signed graph, and L(Γ)L(Γ) be its Laplacian and L(Γ)L(Γ) its normalized Laplacian with eigenvalues λ1≥λ2≥⋯≥λnλ1≥λ2≥⋯≥λn and μ1≥μ2≥⋯≥μnμ1≥μ2≥⋯≥μn, respectively. It is known that a signed graph ΓΓ is balanced if and only if λn=0λn=0 (or μn=0μn=0). We show that λnλn and μnμn measure how much ΓΓ is far from being balanced by proving that
μn(Γ)λn(Γ)≤min{2ϵ(Γ)m,ν(Γ)ν(Γ)+ν1(Γ)},≤min{λ1(Γ′):Γ−Γ′isbalanced},
μn(Γ)≤min{2ϵ(Γ)m,ν(Γ)ν(Γ)+ν1(Γ)},λn(Γ)≤min{λ1(Γ′):Γ−Γ′isbalanced},
where ν(Γ)ν(Γ) (resp. ϵ(Γ)ϵ(Γ)) denotes the frustration number (resp. the frustration index) of ΓΓ, that is the minimum number of vertices (resp. edges) to be deleted such that the signed graph is balanced.
