Archive for May, 2009

Funnily enough, a few days after I wrote the previous post, I was linked to a graph theory paper where one of the first results cited, which was clearly well-known to the authors, is the following remarkable generalization of what I tried to do:

Theorem: The only connected simple graphs with spectral radius less than or equal to \ 2 are the induced subgraphs of the Dynkin diagrams \tilde{A}_n, \tilde{D}_n, \tilde{E}_6, \tilde{E}_7, \tilde{E}_8.

I have to admit, I really didn’t suspect that the classification result I was going after was both so simple and so interesting! Certainly there are heuristic reasons why the above classification makes sense: as I forgot to note in the previous post, there really can’t be too many vertices of degree 3 in a graph with \rho(G) \le 2. But I really can’t fathom why spectral radius can be used to define the Dynkin diagrams, considering their relationship to

simply laced Lie groups,

binary polyhedral groups and the Platonic solids,

quiver representations, or

the octonions (okay, this one is stretching it a little).

Anyone know any good references?

In any case, I’d like to discuss the McKee-Smyth paper because it has some interesting ideas I’d thought about independently.


Read Full Post »


Get every new post delivered to your Inbox.

Join 359 other followers