Spectral Graph Theory and its Applications

2007/10/01 by Daniel A. Spielman · 237 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Graph Labeling and Dimension Problems #Eigenvalues and eigenvectors #Spectral graph theory #Intuition #Graph theory #Computer science #Graph #Mathematics #Theoretical computer science #Combinatorics #Voltage graph #Line graph #Physics #Cognitive science #Quantum mechanics

paper · doi:10.1109/focs.2007.56

openalex publication_date 2007/10/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/29

Abstract

Spectral graph theory is the study of the eigenvalues and eigenvectors of matrices associated with graphs. In this tutorial, we will try to provide some intuition as to why these eigenvectors and eigenvalues have combinatorial significance, and will sitn'ey some of their applications.

Citations

• Eigenvalues and expanders
• Isomorphism of graphs with bounded eigenvalue multiplicity
• How to Draw a Graph
• Power and Centrality: A Family of Measures
• Authoritative sources in a hyperlinked environment
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Simple Constructions of Almost k‐wise Independent Random Variables
• Spectral partitioning works: Planar graphs and finite element meshes
• A new proof of Szemerédi's theorem

Cited by

• Pseudorandom generators for polynomials [wikipedia]