Spectral Properties

Graph Theory · Axiom Academy

LESSON Spectral Properties of Graphs What graph eigenvalues reveal about structure and connectivity 1. Zero Laplacian Eigenvalues and Connected Components The Laplacian matrix L = D - A (where D is the degree matrix and A is the adjacency matrix) has a special property: the number of zero eigenvalues equals the number of connected components in the graph. 2. Second Smallest Eigenvalue: Algebraic Connectivity The second-smallest eigenvalue of the Laplacian, denoted λ₂, is called the algebraic connectivity (or Fiedler value). It measures how well-connected the graph is. λ₂ = 0 if and only if the graph is disconnected Larger λ₂ indicates stronger connectivity The eigenvector associated with λ₂ (Fiedler vector) can partition the graph 3. Largest Adjacency Eigenvalue Bound The largest eigenvalue λ₁ of the adjacency matrix provides bounds on the maximum degree Δ of the graph. 4. Eigenvalue Bounds on Chromatic Number The chromatic number χ(G)—the minimum number of colors needed to color vertices so no adjacent vertices share the same color—can be bounded using eigenvalues. 5. Spectral Gap and Expansion Properties The spectral gap is the difference between the largest and second-largest eigenvalue (in absolute value). It measures the expansion properties of the graph.

This is the written version of the interactive lesson above. See the full Graph Theory course.