Combinatorial and spectral properties of graphs and association schemes
Date
2018
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
The main topics of this dissertation are related to spectral graph theory, a
subtopic of algebraic combinatorics. Algebraic combinatorics is the area of mathematics
that implements techniques from linear and abstract algebra to solve problems in
combinatorics as well as techniques from combinatorics to study algebraic structures.
Spectral graph theory focuses on the study of the eigenvalues associated with various
matrices for a graph and how the eigenvalues relate to structural properties of the
graph. Properties such as connectedness, diameter, independence number, chromatic
number and regularity, among others, are all related to the spectrum of a graph. In this
dissertation we will study the spectra of various graphs and incorporate well known
techniques in spectral graph theory to gain a better understanding of the structure of
these graphs. We focus on three topics (Chapters 2, 3 and 4). The variation of these
topics reinforces how diverse and useful spectral techniques in graph theory can be. ☐ In Chapter 1 we cover notation and basic definitions used throughout this dissertation.
We also introduce some well known and powerful results relating the structural
properties of a graph to its spectrum. This includes a discussion of the properties of
graphs that can be established from the spectrum as well as which graphs are determined
by their spectrum. Finally, we give definitions and basic results for association
schemes and distance-regular graphs since the results of this dissertation are related to
these structures. ☐ In Chapter 2 we study the smallest eigenvalues for distance-j graphs in both
the Hamming and Johnson association schemes. Our results for distance-j Hamming
graphs settle a conjecture proposed by Van Dam and Sotirov in [29]. In fact, we reach
a stronger conclusion than the one proposed by Van Dam and Sotirov. Our results for
x
distance-j Johnson graphs settle a conjecture proposed by Karloff in [46]. Again, we
are able to obtain a stronger conslusion than what is presented in Karloff's conjecture. ☐ In Chapter 3 we use the technique of Godsil-McKay switching to construct
cospectral mates for graphs formed by taking the union of relations in the Johnson
association scheme. Our results offer insight into which graphs in this scheme are not
determined by their spectrum. Our work also unifies the switching sets previously
found for Johnson graphs in [26] and Kneser graphs in [43]. We also present some
open problems related to our work, including a switching set that we would like to see
generalized in order to obtain a new infinite family of graphs in the Johnson scheme
that are not determined by their spectrum. ☐ In Chapter 4 we examine connectivity properties of distance-regular graphs
and graphs related to association schemes. In particular, we prove a result on the
minimum number of edges that need to be deleted from a distance-regular graph in
order to disconnect it into nonsingleton components. We also prove a result on the
edge-connectivity of distance-j twisted Grassmann graphs which supports a conjecture
proposed by Godsil in [35]. Finally, we end the chapter by presenting open problems
dealing with the connectivity of color classes in association schemes.
Description
Keywords
Pure sciences, Association schemes, Distance-regular graphs, Graphs, Linear algebra, Spectral graph theory