Graph theory and complex networks

In the past ten years,the fast development of complex network theory has provided a goodsupport for the study of complexity and complex systems, sincethey describe clearly the important characteristics of complexsystems, and show bright prospects in theory and applications.This paper presents mainly the application of graph theory tocomplex networks, especially to the synchronization problem ofcomplex networks. First, its application to the estimations ofsmallest nonzero, largest eigenvalues and synchronizability indexof certain graphs are commented, followed by the effects ofsubgraph and graph eigenvector in the estimation ofsynchronizability index. Furthermore, the complexity between therelationships of synchronizability and network structuralparameters are discussed via two simple graphs, and the effects ofcomplementary graph, edge-addition and graph operation on thesynchronization of complex networks are elaborated. Finally, somepossible development directions in complex networks are predictedfrom the viewpoint of graph and control theory.