Balancedness and the least eigenvalue of Laplacian of signed graphs

Abstract 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 ⩾ λ 2 ⩾ ⋯ ⩾ λ n ⩾ 0 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 ( Γ ) ⩽ ν ( Γ ) ⩽ ϵ ( Γ ) . 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