
Discrete Mathematics and Optimization Seminar

Nov. 24, 2008
Recent developments in spectral graph theory
Sebastian Cioaba
University of Toronto

Spectral graph theory studies the connections between the structure of a
graph and its eigenvalues. The most studied eigenvalues are the largest
(related to regularity of graph and its chromatic number), the second
largest (which shows if the graph is an expander) and the smallest (related
to the independence number of a graph and also, measuring how bipartite the
graph is). I will present some old and new connections between the spectrum
of a graph and its structure and I will show that other eigenvalues contain
relevant graph information as well.



