Simić, Slobodan K.; matematični kolokvij november 2002

Iz MaFiRaWiki

Eigenspaces of Graphs - A Survey Lecture

Slobodan K. Simić

University of Belgrade, Dept. of Electrical Engineering

14. november 2002


A spectral graph theory is mainly concerned with relations between spectral data and structural properties of graphs. It was very early recognized that the eigenvalues of graphs (as numeric invariants) were not enough to characterize graphs up to isomorphism. In contrast, graphs are determined by their eigenvalues and eigenspaces. Concerning eigenspaces (and their representations) there are a lot of difficulties (like, multiple choice of basis for the eigenspaces, multiple choice of labelling of vertices which induce the order of coordinates of eigenvectors etc). Some ideas to overcome these difficulties can be either to find some canonical bases and/or labellings of vertices (difficult since isomorphism problem then involved), or to derive some new spectral invariants (easy to handle) but, of course, not enough to determine the graphs up to isomorphism. Both possibilities were discussed in the book Eigenspaces of Graphs (by D. Cvetković, P. Rowlinson and S. Simić). In this lecture, we shall select some interesting ideas included in this book, and some new results later developed (by various authors).

Osebna orodja