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 GG if and only if G˙\dot{G} is switching equivalent to GG or its negation. It is proved that the length kk 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 GG. Finally, a relation between kk and characteristic polynomials of G˙\dot{G} and GG is established.

Keywords

• adjacency matrix
• eigenvalue
• walk
• spectral radius
• negative cycle
• 05c50
• 05c22