CanaDAM 2011 University of Victoria, May 31 - June 3, 2011 www.cms.math.ca//2011

Spectral Graph Theory
Org: Bojan Mohar and Steve Kirkland (Simon Fraser University)
[PDF]

AZHVAN SHEIKH AHMADY, Simon Fraser University
Eigenvalues of graphs with many vertices of large degree  [PDF]

A graph with many vertices of large degree that are pairwise at distance at least four from each other, has many large eigenvalues. It’s shown that this does not hold if vertices of large degree are at mutual distance three from each other. We explore this class of graphs further and find some bounds on their eigenvalues. This is joint work with Bojan Mohar and Rayman Singh.

STEVE BUTLER, UCLA
Forming graphs which are cospectral for the normalized Laplacian  [PDF]

We give a method to construct cospectral graphs for the normalized Laplacian. Namely, we can sometimes replace a small bipartite graph with another bipartite graph which is cospectral to it without changing the spectrum of the entire graph. When the bipartite graphs that are switched are regular we can show that the two resulting graphs are cospectral with respect to several other matrices. As an application we produce exponentially large families of cospectral graphs.

SEBASTIAN CIOABA, University of Delaware
Eigenvalues and the structure of graphs.  [PDF]

In this talk, I describe some old and more recent relations between the eigenvalues of a regular graph and its structure.

BOJAN MOHAR, Simon Fraser University
Spectrally degenerate graphs  [PDF]

The spectral radius of a $d$-degenerate graph of maximum degree $D$ is $\le\sqrt{4dD}$. Following this, we say that $G$ is spectrally $d$-degenerate if every subgraph $H$ has spectral radius $\le\sqrt{d\Delta(H)}$. The following rough converse will be presented: Every spectrally $d$-degenerate graph $G$ contains a vertex of degree $\le4d\log_2(\Delta(G)/d)$ (if $\Delta(G)\ge2d$). The dependence on $\Delta$ cannot be eliminated. The proofs involve probabilistic techniques. This is joint work with Zdenek Dvorak.

The trace norm of graphs has been extensively studied under the name of graph energy. The trace norm of a matrix is just one of its Ky Fan $k$-norms, equal to the sum of its $k$ largest singular values. This talk presents extremal results about Ky Fan norms of graphs and matrices. Relations to chromatic number, spectral radius, spread, and to other fundamental parameters are given.