Title：Which graph properties are characterized by the spectrum?
Speaker：Willem Haemers（Tilburg University of Economics and Management, Holland）
Abstract：Spectral graph theory deals with the relation between the structure of a graph and the eigenvalues (spectrum) of an associated matrix, such as the adjacency matrix A and the Laplacian matrix L. Many results in spectral graph theory give necessary condition for certain graph properties in terms of the spectrum of A or L. Typical examples are spectral bounds for characteristic numbers of a graph, such as the independence number, the chromatic number, and the isoperimetric number. Another type of relations are characterization. These are conditions in terms of the spectrum of A or L, which arc necessary and sufficient for certain graph properties. Two famous examples are: (i) a graph is bipartite if and only if the spectrum of A is invariant under multiplication by 1, and(ii) the number of connected components of a graph is equal to the multiplicity of the eigenvalue 0 of L. In this talk we will survey graph properties that admit such a special characterization.