Walks and eigenvalues of signed graphs

Abstract

In this article, we consider the relationships between walks in a signed graph G ˙ \dot{G} and its eigenvalues, with a particular focus on the largest absolute value of its eigenvalues ρ (G ˙) \rho \left(\dot{G}), known as the spectral radius. Among other results, we derive a sequence of lower bounds for ρ (G ˙) \rho \left(\dot{G}) expressed in terms of walks or closed walks. We also prove that ρ (G ˙) \rho \left(\dot{G}) attains the spectral radius of the underlying graph G G if and only if G ˙ \dot{G} is switching equivalent to G G or its negation. It is proved that the length k k of the shortest negative cycle in G ˙ \dot{G} and the number of such cycles are determined by the spectrum of G ˙ \dot{G} and the spectrum of G G. Finally, a relation between k k and characteristic polynomials of G ˙ \dot{G} and G G is established.