Stability of dynamical systems on a graph

We study the stability of large-scale discrete-time dynamical systems that are composed of interconnected subsystems. The stability of such systems is a function of both the dynamics and the interconnection topology. We investigate two notions of stability; the first is connective stability, where the overall system is stable in the sense of Lyapunov despite uncertainties and time-variations in the coupling strengths between subsystems. The second is the standard notion of asymptotic (Schur) stability of the overall system, assuming all interconnections are fixed at their nominal levels. We make connections to spectral graph theory, and specifically the spectra of signed adjacency matrices, to provide graph theoretic characterizations of the two kinds of stability for the case of homogeneous scalar subsystems. In the process, we derive bounds on the largest eigenvalue of signed adjacency matrices that are of independent interest.