Colloquium:Extremizing algebraic connectivity subject to certain graph-theoretic constraints

2004-11-18

4:10 p.m. Neill Hall 5W

Shaun Fallat

Abstract: For a given graph G, its Laplacian matrix is defined to be L=D-A, where A is the (0,1)-adjacency matrix for G and D is the diagonal matrix of vertex degrees for G. The algebraic connectivity of G is the second smallest eigenvalue of the singular matrix L. A simple application of Gersgorin's disc theorem reveals that L is a symmetric positive semidefinite matrix, and an even closer inspection also shows that L is an M-matrix. In this talk we will exploit nonnegative-matrix theory techniques to determine the graphs, which minimize and maximize the algebraic connectivity over all graphs with fixed diameter and fixed girth.