Algebraic Graph Theory Seminar - Bogdan Nica

Monday, November 28, 2022 11:30 am - 11:30 am EST (GMT -05:00)

Title: A recursive spectral bound for independence

Speaker: Bogdan Nica
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.