Skip to main content

Martin Evertsson: Spectral graph theory and graph connectivity

Time: Tue 2020-01-28 15.00 - 16.00

Location: Kräftriket, house 5, room 14

Participating: Martin Evertsson

Export to calendar

Abstract

The second smallest eigenvalue of the Laplacian matrix of a graph, also known as the algebraic connectivity, is an important measure of how strongly a graph is connected. The algebraic connectivity also characterizes the performance of some dynamic processes on networks such as consensus in multiagent networks and synchronization of coupled oscillators. In this paper, we study the problem of bounding the algebraic connectivity of graphs and use the well-known theorems of Courant-Fischer and the Rayleigh-quotients to explicitly bound this eigenvalue for the path graph on \(n\) vertices.