Balancedness and the least eigenvalue of Laplacian of signed graphs

Let Γ=(G,σ) be a connected signed graph, where G is the underlying simple graph and σ:E(G)→{1,−1} is the sign function on the edges of G. Let L(Γ)=D(G)−A(Γ), be the Laplacian of Γ and λ1\geqλ2\geq⋯\geqλn\geq0 be its eigenvalues. It is well-known that a signed graph Γ is balanced if and only if λn(Γ)=0. Here we show that, if Γ is unbalanced, then λ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(Γ)\leq ν(Γ)\leq ϵ(Γ). Further we analyze the case when λn(Γ)=ν(Γ). In the latter setting, we identify the structure of the underlying graph G and we give an algebraic condition for L(Γ) which leads to the above equality.