I got the Estrada book, and am going through it. It covers a lot of ideas.
I find this subject, which is mentioned there, to intriguing:
Wikipedia: [Spectral Graph Theory](http://en.wikipedia.org/wiki/Spectral_graph_theory)
The general idea is to look at graphs in terms of the eigenvalues of their adjacency matrices.
What is the meaning of this approach? I didn't read much about it, but as an exercise here I'll try to think out the beginnings of it.
The adjacency matrix of a graph is just a representation for a binary relation A on a set S. Once we talk about eigenvalues, that means we're thinking of it as a linear transformation T from R^n to R^n, where n is the number of elements in S. The natural basis of R^n corresponds to the members of S. For s in S, T(s) is the set of elements that are connected to s through the relation.
So what are the eigenvectors of T? Here are some simple examples:
* If S0 is a subset of S which doesn't relate to anything through A, then A(S0) is the empty set, so the characteristic function of S0 is a null vector of T. I.e., a set of isolated nodes in the graph has eigenvalue 0.
* If S0 is a subset of S which gets permuted by A -- the set of nodes in an isolated cycle -- then the characteristic function of S0 is a fixed point of T i.e. an eigenvector with eigenvalue 1. A union of such cycles will also have eigenvalue 1.
* The characteristic function of an isolated clique of N elements will be an eigenvector with eigenvalue N. Same for a union of N-cliques.
Other examples? What could be the graph-theoretic interpretation of eigenvectors with non-integer eigenvalues?