EVENT: Groups and Combinatorics Seminar: The characteristic polynomial of a graph

Time and place: 16:00 Friday 10 June in Blakers LT

Speaker: Gordon Royle (UWA)

Title: The characteristic polynomial of a graph

Abstract: The characteristic polynomial of a graph G is the characteristic polynomial of its adjacency matrix.  While there are many different graph polynomials (chromatic, Tutte, matching etc), the characteristic polynomial is perhaps the most heavily studied of all, primarily  because the roots of the characteristic polynomial (i.e. the eigenvalues of its adjacency matrix) carry so much information about structure of the graph and its subgraphs. Indeed, a large proportion of the entire field of algebraic graph theory can be viewed as exploring exactly which properties of graphs are, or are not, reflected in its spectrum. In this talk, I will outline some of the main properties of the characteristic polynomial of a graph, but also introduce some of the interesting open questions that remain. As an example, it is not currently known whether or not almost all graphs are determined up to isomorphism by their characteristic polynomials.