Date of Award
Summer 8-15-2015
Degree Name
Doctor of Philosophy (PhD)
Degree Type
Dissertation
Abstract
Given a graph G we can form a matrix A_G indexed by the vertices of G and which encodes the edges of G. A_G is called the adjacency matrix of G. From the adjacency matrix we may find the eigenvalues. We would now like to know what information we may garner from the eigenvalues. It turns out quite a bit may be determined from the eigenvalues, collectively called the spectrum.
One big question is to ask whether or not a graph can be uniquely determined by its spectrum. Much research has been done in this area, and it is conjectured that almost all graphs may in fact be determined by their spectra. This is however a difficult task. In this dissertation we look at a subset of all graphs, namely those with either -1 or 0 in their spectrum with a given multiplicity. We first show that any such graph must either be primitive in a sense, or that it is obtained from a primitive graph by an elementary operation of blowing up or splitting vertices. We then show that the set of primitive graphs is finite, for a fixed multiplicity. Lastly, we analyze graphs with -1 or 0 in their spectra with multiplicities up to 4, and show many which are uniquely determined by their spectra.
Language
English (en)
Chair and Committee
John Shareshian
Committee Members
Renato Feres, Robert Pless, Ari Stern, David Wright
Recommended Citation
Boyett, Casey, "Graphs with Eigenvalues of High Multiplicity" (2015). Arts & Sciences Electronic Theses and Dissertations. 636.
https://openscholarship.wustl.edu/art_sci_etds/636
Comments
Permanent URL: https://doi.org/10.7936/K7ZK5DXR