A Class of Optimal Directed Graphs for Network Synchronization

In a paper by Nishikawa and Motter, a quantity called the normalized spread of the Laplacian eigenvalues is used to measure the synchronizability of certain network dynamics. Through simulations, and without theoretical validation, it is conjectured that among all simple directed graphs with a fixed number of vertices and arcs, the optimal value of this quantity is achieved if the Laplacian spectrum satisfies a specific pattern. This paper proves this conjecture and further shows that the conjectured spectral condition is not only sufficient but also necessary. Moreover, the paper proves that the optimal Laplacian spectrum is always achievable by a class of almost regular directed graphs, which can be constructed through an inductive algorithm.