Graph Spectra and the Adjacency Matrix

Spectral graph theory studies graphs through the eigenvalues and eigenvectors of associated matrices. The spectrum encodes structural information about connectivity, expansion, chromatic number, and random walks.

Adjacency Matrix Spectrum

Definition8.1Adjacency Matrix and Spectrum

The adjacency matrix $A(G)$ of a graph $G$ on $n$ vertices has $A_{ij} = 1$ if $ij \in E$ and $0$ otherwise. The spectrum is the multiset of eigenvalues $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ . Key properties: $\sum \lambda_i = 0$ (trace is 0 for simple graphs); $\sum \lambda_i^2 = 2|E|$ (trace of $A^2$ ); $\sum \lambda_i^k$ counts closed walks of length $k$ .

ExampleSpectra of Basic Graphs

Complete graph $K_n$ : eigenvalues $n-1$ (multiplicity 1) and $-1$ (multiplicity $n-1$ ).
Complete bipartite $K_{a,b}$ : eigenvalues $\pm\sqrt{ab}$ (each multiplicity 1) and $0$ (multiplicity $a+b-2$ ).
Cycle $C_n$ : eigenvalues $2\cos(2\pi k/n)$ for $k = 0, 1, \ldots, n-1$ .
Path $P_n$ : eigenvalues $2\cos(k\pi/(n+1))$ for $k = 1, \ldots, n$ .

Spectral Characterizations

Definition8.2Spectral Radius and Graph Properties

The spectral radius $\lambda_1 = \rho(G)$ satisfies: $\bar{d} \leq \lambda_1 \leq \Delta$ (between average and max degree), with $\lambda_1 = \Delta$ iff $G$ is $\Delta$ -regular. The chromatic number satisfies $\chi(G) \geq 1 + \lambda_1/|\lambda_n|$ (Hoffman bound). The independence number satisfies $\alpha(G) \leq n \cdot |\lambda_n|/(\lambda_1 + |\lambda_n|)$ (Hoffman-Lovász bound).

RemarkCospectral Graphs

Two graphs are cospectral if they have the same spectrum but are non-isomorphic. Example: $C_4 \cup K_1$ and $K_{1,4}$ both have spectrum $\{2, 0, 0, 0, -2\}$ . The spectrum does not determine the graph, but the fraction of graphs with a cospectral mate tends to 0 (Schwenk). Graphs determined by their spectrum include: $K_n$ , $K_{n,n}$ , and many strongly regular graphs.