From weighted to unweighted graphs in Synchronizing Graph Theory

Abstract

A way to associate unweighted graphs from weighted ones is presented, such that linear stable equilibria of the Kuramoto homogeneous model associated to both graphs coincide, i.e., equilibria of the system ${\dot{\theta }}_i={\sum }_{j\sim i}\sin ({\theta }_j-{\theta }_j)$, where $i\sim j$ means vertices $i$ and $j$ are adjacent in the corresponding graph. As a consequence, the existence of linearly stable equilibrium is proved to be NP-Hard as conjectured by R. Taylor in 2015 and a new lower bound for the minimum degree that ensures synchronization is found.