Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Combinatorics Seminar

Sebi Cioaba

UCSD

Eigenvalues and eigenvectors of irregular graphs

Abstract:

The eigenvalues of regular graphs have been well studied. They have strong connections with the expansion constant (Alon-Milman, Tanner), diameter (Chung), chromatic and independence number (Hoffman) of a graph. In this talk, I will discuss the eigenvalues of irregular graphs. One of the first results of spectral graph theory due to Collatz and Sinogowitz (1957) states that the spectral radius of a graph is between the average degree and the maximum degree of a graph with equality iff the graph is regular. When the graph is irregular, I will show how can we improve these inequalities. I will conclude with a list of open problems. This is based on joint work with David Gregory (Queen’s University at Kingston, Canada) and Vlado Nikiforov (University of Memphis, USA).

July 24, 2006

2:00 PM

AP&M 7321

****************************