Preface

Summary

The foundations of spectral graph theory were laid in the fifties and sixties, as a result of the work of a considerable number of mathematicians. Most of the early results are, like this book, concerned with the relation between spectral and structural properties of a graph. The investigation of such a relationship was proposed explicitly by Sachs [Sacl] and Hoffman [Hof5], although in effect it had already been initiated in an earlier article by Collatz and Sinogowitz [CoSi]. This seminal paper appeared in 1957, but our bibliography contains two references prior to this date: the unpublished thesis of Wei [Wei] from 1952, and a summary (also unpublished) of a 1956 paper by Lihtenbaum [Lih] communicated at the 3rd Congress of Mathematicians of the U.S.S.R.

Another origin of the theory of graph spectra lies beyond mathematics. In quantum chemistry, an approximative treatment of non-saturated hydrocarbons introduced by E. Huckel [Hue] yields a graph-theoretical model of the corresponding molecules in which eigenvalues of graphs represent the energy levels of certain electrons. The connection between Huckel's model of 1931 and the mathematical theory of graph spectra was recognized many years later in [GüPr] and [CvGul], and thereafter exploited extensively by many authors, both chemists and mathematicians.

In his thesis [Cve7], Cvetkovic identified 83 papers dealing with eigenvalues of graphs which had appeared before 1970.