|
Friday, July 24, 2009 |
|
|
|
|
Awful Graphs |
|
|
Apparently despite the computational evidence, at the recent BCC Willem Haemers conjectured that almost all graphs are determined by their characteristic polynomial of their adjacency matrix. I will describe recent work that offers strong support for this conjecture, based on the concept of "awful" graphs. An $n$-vertex graph is awful if its adjacency matrix $A$ and the all-ones matrix $J$ together generate the algebra of all $n\times n$. I will describe some of the theory of this class of graphs, and show how it supports Haemers' conjecture. |