Simple eigenvalues of graphs and digraphs

Author: 
Date created: 
2015-01-26
Identifier: 
etd8852
Keywords: 
Algebraic graph theory
Eigenvalues
Linear algebra
Directed graphs
Abstract: 

The spectra of graphs and their relation to graph properties have been well-studied. For digraphs, in contrast, there are relatively few results. The adjacency matrix of a digraph is usually difficult to work with; it is not always diagonalizable and the interlacing theorem does not hold (in general) for adjacency matrices of digraphs. All acyclic digraphs have the same spectrum as the empty graph. This motivates the need to work with a different matrix which captures the adjacency of the digraph. To this end, we introduce the Hermitian adjacency matrix. Another way to extract more information out of the spectrum is by restricting to specific classes of digraphs. In this thesis, we look at vertex-transitive digraphs with simple eigenvalues. Intuitively, the property of having many simple eigenvalues tends to coincide with having few automorphisms. For example, the only vertex-transitive graph with all eigenvalues simple is K_2. In the case of graphs, we restrict to the cubic vertex-transitive case, where we find combinatorial properties of graphs with multiple simple eigenvalues. We also explore the eigenvectors of vertex-transitive digraphs with all eigenvalues distinct.

Document type: 
Thesis
Rights: 
Copyright remains with the author. The author granted permission for the file to be printed and for the text to be copied and pasted.
File(s): 
Senior supervisor: 
Bojan Mohar
Department: 
Science:
Thesis type: 
(Dissertation) Ph.D.
Statistics: