Introduction

Spectral Graph Theory book. Read 3 reviews from the world's largest community for readers. Based on 10 lectures given at the CBMS workshop on spectral gr. Spectral graph drawing: FEM justification If apply finite element method to solve Laplace’s equation in the plane with a Delaunay triangulation Would get graph Laplacian, but with some weights on edges Fundamental solutions are x and y coordinates (see Strang’s Introduction to Applied Mathematics).

Spectral graph theory looks at the connection between the eigenvalues of a matrix associated with a graph and the corresponding structures of a graph. The four most common matrices that have been studied for simple graphs (i.e., undirected and unweighted edges) are defined by associating the vertices with the rows/columns as follows.

The adjacency matrixA which is defined by placing a 1 in an entry in which there is an edge and a 0 otherwise.
The (combinatorial) LaplacianL:=D-A where D is the diagonal matrix of degrees and A is the adjacency matrix.
The signless LaplacianQ:=D+A where D is the diagonal matrix of degrees and A is the adjacency matrix.
The normalized LaplacianL:=D^-1/2LD^-1/2 where D is the diagonal matrix of degrees and L is the combinatorial Laplacian. By convention when a vertex has degree 0 (i.e., is isolated) then the corresponding entry of D^-1/2 is 0.

There are many simple properties of graphs that can be deduced from the eigenvalues of the matrices. For example, the number of edges (via the adjacency, Laplacian and signless Laplacian), the number of connected components (via the adjacency, Laplacian and normalized Laplacian), being bipartite (via the adjacency and normalized Laplacian), and the number of bipartite components (via the signless Laplacian). For many people this is the extent to which they see the eigenvalues of matrices applied to graphs, and while these are interesting graph parameters to measure they do not show the strength of spectral graph theory.

We have gathered here a collection of various applications that have been developed that use spectral graph theory, sometimes in a surprising and unexpected way, to the study of graphs. This list is not meant to be exhaustive, but rather to give a taste for what is possible to do with the eigenvalues of a graph.

Useful surveys

More information about spectral graph theory and some of the applications in the wild, can be found in several monologues and surveys.

Spectra of graphs -- a survey of spectral graph theory written by Andries Brouwer and Willem Haemers. This is one of the best places to start learning about spectral graph theory.
Some applications of the Laplace eigenvalues of graphs -- a survey of applications of the combinatorial Laplacian written by Bojan Mohar, fairly comprehensive on what can be done with the Laplacian.
Eigenvalues in combinatorial optimization -- a survey written by Bojan Mohar and Svatopluk Poljak.
Spectral theory of graphs based on the signless Laplacian -- a survey of the signless Laplacian written by Dragos Cvetkovic. This contains material from several surveys about the signless Laplacian and is a good introduction to why it is an interesting matrix and how it connects to other matrices.
Spectral graph theory -- a book focused on the definition and development of the normalized Laplacian written by Fan Chung, the first four chapters of the revised version are available online. This is the classic book for the normalized Laplacian.
Spectral graph theory and its applications -- a class website for a course taught at Yale by Dan Spielman. Includes several lecture notes with some applications.
Graph spectra in computer science -- a set of slides prepared by Dragos Cvetkovic giving an overview of applications of spectral graph theory to computer science, includes useful references and pointers to other papers. Also the paper version has appeared written by Dragos Cvetkovic and Slobodan Simic.
- The slides includes the following quote: 'Our general suggestion is that mathematicians should react on the explosion of the number of papers in computer science which use graph spectra by selecting for their own research some subjects from or inspired by such applications.'

Applications of eigenvalues

Showing that two graphs are non-isomorphic. If two graphs have differing sets of eigenvalues for some matrix then the graphs cannot be isomorphic (i.e., same up to relabeling). As a result many papers in spectral graph theory deal with deciding what eigenvalues can and cannot distinguish and showing that certain graphs are uniquely determined by their eigenvalues. A major problem is that many graphs have cospectral mates and so cannot be determined by their spectrum.
Hoffman bound for the chromatic number, and various extensions. (See, for example, the paper Tales of Hoffman: Three extensions of Hoffman's bound on the graph chromatic number by Yonatan Bilu for some extensions. The original bound is classical and can be found in the survey by Andries Brouwer and Willem Haemers.)
Finding small Folkman graphs, i.e., graphs with no K₄ but any 2-coloring contains a monochromatic K₃. (See the paper Explicit construction of small folkman graphs by Lincoln Lu.)
Graham-Pollak Theorem which shows that K_n cannot be decomposed into fewer than n-1 complete bipartite graphs. (There are many proofs of this classical result, curiously they almost all rely on linear algebra in some way.)
Rate of convergence of random walks. This is closely tied to the normalized Laplacian, since the eigenvalues of the normalized Laplacian are the same as those of the probability transition matrix of a random walk. (This is a well studied topic. See, for example, chapter 1.5 in the book of Fan Chung.)
Lower bounds for the size of matchings in graphs. (This has been well studied by Sebi Cioaba and coauthors. See, for example, Edge-connectivity, eigenvalues and matchings in regular graphs by Suil O and Sebastian Cioaba and Matchings in regular graphs from eigenvalues by Sebastian Cioaba, David Gregory and Willem Haemers.)
Counting triangles in graphs, more generally counting the number of closed walks of length k by looking at the eigenvalues of the adjacency. Related to this is the paper Lower bounds on the number of triangles in a graph by David Fisher which uses eigenvalues of the complement of a graph to give a lower bound for a root of a certain polynomial which relates to density of complete graphs, in particular triangles.
Lovasz theta function gives a method to bound the Shannon capacity of a graph. In general this is very hard, but some results are known for some graphs, such as C₅ by using eigenvalue bounds. (This can be found in On the Shannon capacity of a graph by Laszlo Lovasz, also in Proofs from the book by Martin Aigner and Gunter Ziegler.)
The graph K₁₀ cannot be (edge) decomposed into a union of three copies of a Petersen graph. (The number of edges is not enough to rule this out, see the survey by Brouwers and Haemers for a proof.)
Showing a graph is Hamiltonian. One approach is to show that a graph is quasi- or pseudo-random and then use properties about such graphs. This approach was used to great effect in Sparse pseudo-random graphs are Hamiltonian by Michael Krivelevich and Benny Sudakov (this was modified to show that one can drop the assumptions of regularity in Small spectral gap in the combinatorial Laplacian implies Hamiltonian by Steve Butler and Fan Chung). An alternative approach is to show that a graph has high minimum degrees. This was done in Spectral radius and Hamiltonicity of graphs by Miroslav Fiedler and Vladimir Nikiforov.
Bounding discrepancy in graphs, a measurement of the maximum difference in the number of e

Spectral Graph Theory Book