We work with mixed graphs, where some connections are undirected and others are directed. We study them using the Hermitian adjacency matrix and the Hermitian Laplacian. These matrices record both the underlying graph and the directions, and their eigenvalues change in a controlled way when we “switch” phases at vertices. A mixed graph is called balanced if a switching can remove all direction-phases. We measure how far a graph is from being balanced by frustration parameters: the minimum number of vertices or connections that must be removed to make the graph balanced. Using these parameters, we give explicit upper bounds on the smallest Hermitian Laplacian eigenvalue for connected unbalanced mixed graphs. We also give a bound that localizes this eigenvalue using a shortest frustrated cycle and its boundary. We then study the independence number. We prove a Hoffman-type upper bound that works without any regularity assumption by adding a variance term that measures how far the Hermitian row sums are from being constant. This variance changes under switching, so the bound can be improved by choosing a good switching. Paley-type examples show that the resulting bound can be much stronger than the inertia bound.
Abudayah et al. (Fri,) studied this question.