Printable PDF
Department of Mathematics,
University of California San Diego

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

Math 269 - Combinatorics

Sebastian Cioaba

UCSD

The spectral radius and the diameter of connected graphs

Abstract:

Recently, Wang, Chakrabarti, Wang and Faloutsos have shown that the spectral radius of a graph plays an important role in modeling virus propagation in networks. This led Van Dam and Kooij to consider the following problem: which connected graph on n nodes and diameter D has minimal spectral radius ? Van Dam and Kooij answered this question for $D=n-1,n-2,n-3,n/2,2,1$ and provided a conjecture for the case $D=n-e$, when e is fixed. In this talk, I give an overview of their work and I will outline a proof of their conjecture for $e=4$ and possible extensions for $e>4$. This is joint work in progress with Edwin Van Dam (University of Tilburg, The Netherlands).

April 17, 2007

4:00 PM

AP&M 7321

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