Balancedness and the least eigenvalue of Laplacian of signed graphs

Let Γ=(G,σ)Γ=(G,σ) be a connected signed graph, where G   is the underlying simple graph and σ:E(G)→{1,−1}σ:E(G)→{1,−1} is the sign function on the edges of G  . Let L(Γ)=D(G)−A(Γ)L(Γ)=D(G)−A(Γ), be the Laplacian of Γ   and λ1⩾λ2⩾⋯⩾λn⩾0λ1⩾λ2⩾⋯⩾λn⩾0 be its eigenvalues. It is well-known that a signed graph Γ   is balanced if and only if λn(Γ)=0λn(Γ)=0. Here we show that, if Γ   is unbalanced, then λnλn estimates how much Γ   is far from being balanced. In particular, let ν(Γ)ν(Γ) (resp. ϵ(Γ)ϵ(Γ)) be the frustration number (resp. frustration index), that is the minimum number of vertices (resp. edges) to be deleted such that the signed graph is balanced. Then we prove thatλn(Γ)⩽ν(Γ)⩽ϵ(Γ).λn(Γ)⩽ν(Γ)⩽ϵ(Γ). Further we analyze the case when λn(Γ)=ν(Γ)λn(Γ)=ν(Γ). In the latter setting, we identify the structure of the underlying graph G   and we give an algebraic condition for L(Γ)L(Γ) which leads to the above equality.