05C50 Online Seminar: Carlos Hoppen

The inverse eigenvalue problem has played a central role in spectral graph theory in the last decade. In this talk, I shall be interested in a particular parameter, namely the minimum number of distinct eigenvalues of a graph G, i.e., in the minimum number of distinct eigenvalues of a real symmetric matrix whose underlying graph is G. To be precise, let M be a symmetric matrix of order n. A graph G is said to be the underlying graph of M if its vertex set has n elements and if any pair of distinct vertices i and j are adjacent if and only if the entry ij of M is nonzero. There is no constraint about diagonal entries.

It is well known that, if G is a tree, the value of this parameter is at least d(G)+1, where d(G) is the diameter of G. I will discuss instances where this bound is tight. In a different direction, I will show that the number of eigenvalues of G is at most 4 whenever G is a cograph, that is, whenever G does not contain an induced path on four vertices.

This includes joint work with L. Emilio Allem, Martin Fürer, Lucas Siviero Sibemberg, and Vilmar Trevisan.