CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

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

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.

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.

VLADO NIKIFOROV, University of Memphis
The Ky Fan norms of graphs and matrices  [PDF]

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.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria