Eigenvalues and Laplacian of a Graph: A Useful Lemma

Recently, for one of my projects I have been using the Laplacian matrix to study the spectra of graphs. For this post, I’ll review a tiny bit of background material on matrix theory for spectral graph theory. The majority of the material in this post can be found in the survey by Chung (1997).

What is the significance of eigenvalues and the Laplacian in understanding the properties and structure of graphs? Below, we highlight examples that show a connection between graph eigenvalues and the geometric aspects of graphs.

The Laplacian

Let G be a graph with vertex degree denoted by d_v for vertex v. Consider the following matrix L:

The Laplacian matrix \mathcal{L} is then defined by \mathcal{L} = T^{-1/2}LT^{-1/2}, where T is the diagonal matrix with (v, v)-th entry having value d_v. (This definition of the Laplacian is for graphs without loops and multiple edges.)

Examples

Examples of special graphs and the eigenvalues of their Laplacians:

  1. The star graph S_n on n vertices has eigenvalues 0, 1 (with multiplicity n-2), and 2.
  2. For the complete graph K_n on n vertices, the eigenvalues are 0 and \frac{n}{n - 1} with multiplicity n - 1.
  3. For the path P_n on n vertices, the eigenvalues are 1 - \cos\left(\frac{\pi k}{n-1}\right) for k = 0, 1, \ldots, n - 1.

Basic fact about the spectrum of a graph

Lemma (e.g., see Lemma 1.7 in [1]):
For a graph G on n vertices, we have:

  1. \sum_i \lambda_i \leq n with equality holding if and only if G has no isolated vertices.
  2. If G is connected, then \lambda_1 > 0. If \lambda_i = 0 and \lambda_{i+1} \neq 0, then G has exactly i + 1 connected components.
  3. The spectrum of a graph is the union of the spectra of its connected components.

Exercise for the reader: Can you rewrite the lemma in terms of the Laplacian?

[1] F.R.K. Chung. Spectral Graph Theory. Conference Board of Mathematical Sciences. American Mathematical Society, 1997.

Leave a comment