Extremal graphs with minimal k-th Laplacian eigenvalue

Activity: Talk or presentationScience to science


A method for characterizing graphs that have smallest (or largest)
Laplacian eigenvalue within a particular class of graphs works as
Take a Perron vector, rearrange the edges of the graph and compare the
respective Rayleigh quotients. By the Rayleigh-Ritz Theorem we can draw some conclusions about the change of the smallest eigenvalue. This approach, however, does not work for the k-th Laplacian eigenvalue, as now we have to use the Courant-Fisher
Theorem that involves minimization of the Rayleigh quotients with respect to constraints that are hard to control.
In this talk we show that sometimes we can get local properties of
extremal graphs by means of the concept of "geometric nodal domains"
and "Dirichlet matrices". This is in particular the case for the algebraic connectivity.
Period1 Jul 2009
Event title24th LL-Seminar on Graph Theory
Event typeUnkonwn
Degree of RecognitionNational