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 are the induced subgraphs of the Dynkin diagrams .
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 in a graph with . But I really can’t fathom why spectral radius can be used to define the Dynkin diagrams, considering their relationship to
- 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.