Title: Using eigenvalues to bound the independence number of a graph
|Affiliation:||University of Waterloo|
Finding a maximum independent set (or clique) in an arbitrary graph has been shown to be NP-hard. As any independent set gives a lower bound on the independence number, determining an upper bound is usually more useful. Two such upper bounds are the Hoffman-Delsarte bound and the Cvetković bound. Both use the eigenvalues of a matrix associated with the graph.
I will introduce the two bounds and share some recent results from joint work with Zach Dockstader.