Eigenvalues and structures of graphs.

Given a graph we can associate several matrices which record information about vertices and how they are interconnected.

The question then arises, given that you know the eigenvalues of some matrix associated with the graph, what can you say about the graph?

Spectral graph theory looks at answering questions of this type.

In this dissertation we will be focusing on the eigenvalues of the normalized Laplacian of a matrix which is defined as L = D -1/2(D - A)D-1/2 where D is the diagonal matrix of degrees and A is the adjacency matrix of the graph.

In addition to some background material on spectral graph theory we will be looking at three main results about how eigenvalues and structures of graphs are interrelated.

These are as follows. (1) For any graph (including directed graphs) the edge discrepancy is a measurement of how randomly the edges are placed.

While it has been known for some time that for undirected graphs that a tight clustering of eigenvalues around 1 implies a good measure of discrepancy, only recently has some progress been made in the other direction.

We will show that for any graph (including directed graphs) that a small discrepancy implies a tight clustering of singular values of the normalized adjacency matrix.

This shows that having small discrepancy and a tight clustering of singular values are in the same quasirandom class of properties for directed graphs. (2) Graphs which share common local structure tend to share eigenvalues.

We will consider one type of covering that preserves local structures, namely 2-edge-coverings which, as the name strongly suggests, is a mapping from a graph G to a graph H so that each edge in H is twice covered.

We show how to compute the eigenvalues of G from the eigenvalues of two modified forms of H.

As an application we give a construction of two graphs which are not regular but are cospectral with respect to both the adjacency and normalized Laplacian matrix. (3) Given a graph G, the removal of a small graph will have an effect on the eigenvalues of the graph.

We will show that the new eigenvalues will interlace the old eigenvalues (with the size of the interlacing dependent on the number of vertices in the graph which is removed).

We will also mention some negative results about interlacing and a normalized Laplacian which has been introduced for directed graphs.