Font Size: 

A signed graph $\Gamma$ is a pair $(G,\sigma)$, where $G=(V(G),E(G))$ is a simple graph and $\sigma:E(G)\rightarrow\{1,-1\}$ is the sign function on the edges of $G$. A cycle in $\Gamma$ is said to be positive if and only if the product of its edge signs is positive. A signed graph $\Gamma$ is balanced if all of its cycles are positive. If $\Gamma$ is not balanced, then a suitable deletion of some vertices or edges leads to a balanced graph. Let $\nu(\Gamma)$ (resp. $\epsilon(\Gamma)$) be the minimum number of vertices (resp. edges) to be deleted such that the obtained signed graph is balanced. The values $\nu(\Gamma)$ and $\epsilon(\Gamma)$ are called the frustration number and frustration index, respectively. Let $D(G)$ be the diagonal matrix of vertex degrees, and $A(\Gamma)=(a_{ij})$ be the adjacency matrix of $\Gamma$, where $a_{ij}=\sigma(ij)$ whenever $ij\in E(G)$ and $a_{ij}=0$ otherwise. For any signed graph $\Gamma=(G,\sigma)$, the matrix $L(\Gamma)=D(G)-A(\Gamma)$ is the Laplacian of $\Gamma$, and $\lambda_1\geq \lambda_2\geq \cdots\geq \lambda_n\geq0$ are its eigenvalues.
It is well-known that if $\Gamma$ is a connected balanced graph then $\lambda_n(\Gamma)=0$. Here we show that $\lambda_n(\Gamma)\leq\nu(\Gamma)\leq\epsilon(\Gamma)$. Hence we refer to $\lambda_n(\Gamma)$ as the algebraic frustration. Further, we study the case $\lambda_n(\Gamma)=\nu(\Gamma)$, and we give necessary and sufficient conditions which lead to the latter equality. Finally, we give some families of almost complete signed graphs for which the above equality holds and we compute their spectra.

Signed graph, Least eigenvalue, Laplacian matrix, Balanced signed graph, Frustration