On the Complexity of the Classification of Synchronizing Graphs

Abstract

This article deals with the general ideas of almost global synchronization of Kuramoto coupled oscillators and synchronizing graphs. It reviews the main existing results and gives some new results about the complexity of the problem. It is proved that any connected graph can be transformed into a synchronized one by making suitable groups of twin vertices. As a corollary it is deduced that any connected graph is the induced subgraph of a synchronizing graph. This implies a big structural complexity of synchronizability. Finally the former is applied to find a two integer parameter family G(a,b) of connected graphs such that if b is the k-th power of 10, the synchronizability of G(a,b) is equivalent to find the k-th digit in the expansion in base 10 of the square root of 2. Thus, the complexity of classify G(a,b) is of the same order than the computation of square root of 2. This is the first result so far about the computational complexity of the synchronizability problem.