Considerable effort in modern statistical physics is devoted to the study of networked systems. One of the most important example of them is the brain, which creates and continuously develops complex networks of correlated dynamics. An important quantity which captures fundamental aspects of brain network organization is the neural complexity C(X) introduced by Tononi et al. [Proc. Natl. Acad. Sci. USA 91, 5033 (1994)]. This work addresses the dependence of this measure on the topological features of a network in the case of a Gaussian stationary process. Both analytical and numerical results show that the degree of complexity has a clear and simple meaning from a topological point of view. Moreover, the analytical result offers a straightforward and faster algorithm to compute the complexity of a graph than the standard one.