Spectral and combinatorial properties of friendship graphs, simplicial rook graphs, and extremal expanders
Date
2015
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
Algebraic combinatorics is the area of mathematics that uses the theories and methods of abstract and linear algebra to solve combinatorial problems, or conversely applies combinatorial techniques to solve problems in algebra. In particular, spectral graph theory applies the techniques of linear algebra to study graph theory. Spectral graph theory is the study of the eigenvalues of various matrices associated with graphs and how they relate to the properties of those graphs. The graph properties of diameter, independence number, chromatic number, connectedness, toughness, hamiltonicity, and expansion, among others, are all related to the spectra of graphs. In this thesis we study the spectra of various families of graphs, how their spectra relate to their properties, and when graphs are determined by their spectra. We focus on three topics (Chapters 2-4) in spectral graph theory. The wide range of these topics showcases the power and versatility of the eigenvalue techniques such as interlacing, the common thread that ties these topics together. In Chapter 1, we review the basic definitions, notations, and results in graph theory and spectral graph theory. We also introduce powerful tools for determining the structure of a graph and its subgraphs using eigenvalue interlacing. Finally, we discuss which graph properties can be deduced from the spectra of graphs, and which graphs are determined by their spectra. In Chapter 2, we use eigenvalue interlacing to determine whether the friendship graphs and, more generally, graphs with exactly four distinct eigenvalues, are determined by their spectra. We show that friendship graphs are determined by their adjacency spectra with one exception, settling a conjecture in the literature. We also characterize the graphs with all but two eigenvalues equal to +/-1 and determine which of these graphs are determined by their spectra. In Chapter 3 we study the simplicial rook graphs. We first determine several general properties of these graphs. Next, we determine the spectrum of some sub-families of the simplicial rook graphs, find partial spectra for all simplicial rook graphs, and confirm several conjectures in the literature on the spectra of simplicial rook graphs, including the fact that the simplicial rook graphs have integral spectra. In Chapter 4 we study the second largest adjacency eigenvalue of regular graphs. We determine upper bounds on the number of vertices in a regular graph with various given valencies and second eigenvalues, confirming or disproving many conjectures in the literature. In many cases we find the graphs, often unique, that meet these bounds. These graphs are called extremal expanders. We discuss a linear programming bound that guarantees that distance-regular graphs with certain parameters, if they exist, are extremal expanders. In Chapter 5 we discuss open problems and questions for further research on the topics covered in Chapters 2-4.