Title: A recursive spectral bound for independence
|Affiliation:||Indiana University-Purdue University Indianapolis|
|Location:||Contact Sabrina Lato for Zoom link|
Abstract: We discuss an upper bound for the independence number of a graph, in the spirit of the well-known Hoffman bound. Our bound involves the largest Laplacian eigenvalue of the graph; more surprisingly, it also involves the independence number of a certain induced graph. We illustrate the bound on several examples.