Inequalities for Laplacian Eigenvalues of Signed Graphs with Given Frustration Number

Balanced signed graphs appear in the context of social groups with symmetric relations between individuals where a positive edge represents friendship and a negative edge represents enmities between the individuals. The frustration number f of a signed graph is the size of the minimal set F of vertices whose removal results in a balanced signed graph; hence, a connected signed graph (G) over dot & nbsp;is balanced if and only if f=0. In this paper, we consider the balance of (G) over dot via the relationships between the frustration number and eigenvalues of the symmetric Laplacian matrix associated with (G) over dot. It is known that a signed graph is balanced if and only if its least Laplacian eigenvalue (n) is zero. We consider the inequalities that involve certain Laplacian eigenvalues, the frustration number f and some related invariants such as the cut size of F and its average vertex degree. In particular, we consider the interplay between and f.</p>