Spectral graph theory : from practice to theory

Abstract

Graph theory is the area of mathematics that studies networks, or graphs. It arose from the need to analyse many diverse network-like structures like road networks, molecules, the Internet, social networks and electrical networks. In spectral graph theory, which is a branch of graph theory, matrices are constructed from such graphs and analysed from the point of view of their so-called eigenvalues and eigenvectors. The first practical need for studying graph eigenvalues was in quantum chemistry in the thirties, forties and fifties, specifically to describe the Hückel molecular orbital theory for unsaturated conjugated hydrocarbons. This study led to the field which nowadays is called chemical graph theory. A few years later, during the late fifties and sixties, graph eigenvalues also proved to be important in physics, particularly in the solution of the membrane vibration problem via the discrete approximation of the membrane as a graph. This paper delves into the journey of how the practical needs of quantum chemistry and vibrating membranes compelled the creation of the more abstract spectral graph theory. Important, yet basic, mathematical results stemming from spectral graph theory shall be mentioned in this paper. Later, areas of study that make full use of these mathematical results, thus benefitting greatly from spectral graph theory, shall be described. These fields of study include the P versus NP problem in the field of computational complexity, Internet search, network centrality measures and control theory.