Locating eigenvalues of unbalanced unicyclic signed graphs

A signed graph is a pair Gamma = (G, sigma), where G is a graph, and sigma : E(G) -> {+1, -1} is a signature of the edges of G. A signed graph Gamma is said to be unbalanced if there exists a cycle in Gamma with an odd number of negatively signed edges. In this paper it is presented a linear time algorithm which computes the inertia indices of an unbalanced unicyclic signed graph. Additionally, the algorithm computes the number of eigenvalues in a given real interval by operating directly on the graph, so that the adjacency matrix is not needed explicitly. As an application, the algorithm is employed to check the integrality of some infinite families of unbalanced unicyclic graphs. In particular, the multiplicities of eigenvalues of signed circular caterpillars are studied, getting a geometric characterization of those which are non-singular and sufficient conditions for them to be non-integral. Finally, the algorithm is also used to retrieve the spectrum of bidegreed signed circular caterpillars, none of which turns out to be integral. (C) 2021 Elsevier Inc. All rights reserved.