Inequalities for laplacian eigenvalues of signed graphs with given frustration number

Abstract

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 Ġ is balanced if and only if f = 0. In this paper, we consider the balance of Ġ via the relationships between the frustration number and eigenvalues of the symmetric Laplacian matrix associated with Ġ. 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 µn and f.