Eigenvalues, polynomials, and structure in graphs
|Speaker:||Edwin van Dam|
|Room:||Mathematics & Computer Building (MC) 5158|
The eigenvalues of the adjacency matrix of a graph contain a lot --- but not always all --- information on the structure of the graph. We will review some structural properties that can be derived from the eigenvalues of a graph, and discuss when a graph is determined by its spectrum (of eigenvalues), or how different graphs with the same spectrum can be constructed.
We then dive deeper into graphs that have a lot of combinatorial symmetry: distance-regular graphs. We will see how systems of orthogonal polynomials can help to recognize such graphs from their eigenvalues and a little extra information. We apply this to obtain a recent characterization of the generalized odd graphs by their number of distinct eigenvalues and the length of their shortest odd cycles.
If time permits, we also show how eigenvalues led to the construction of the twisted Grassmann graphs, a family of distance-regular graphs that have the same spectrum as certain Grassmann graphs, but that are not vertex-transitive.
200 University Avenue West
Waterloo, ON N2L 3G1