# Knowledge about Graph Spectral Theory and correlation between a graph Weighted Adjacency matrix and its eigenvalues

I know that this question is some sort of bridge between Informatics and Mathematics, not knowing the best place where to post this question, I opted for this place because of the type of answer I want (which concerns Math more than anything).

Consider to have a graph represented by a collection of nodes and connections. The best way to describe the graph is through the adjacency matrix (AM): a matrix that has 0 or 1 if one node is connected to another (we consider non-directed graphs, so we have all bidirectional connections).

Does anyone know whether the eigenvalues of the matrix implies something for the graph??? properties, topology.... I ask this question because I've almost finished studying Markov Chains. In a chain, the matrix of transition probabilities P (for discrete time markov chains), or the matrix of transition frequencies Q (for cont-time markov chains), can be evaluated (their eigenvalues) in order to inspect whether the chain is ergodic or not (with a parallelism to Control Theory: eigenvalues in the unitary circle or in the negative half-plane).

I am trying to find something similar for graphs.

Thank you

-
–  Aryabhata Feb 9 '11 at 20:52

There are a lot of properties on eigenvalues of adjacency matrix.

If the diameter of $G$ is d, then $A$ has at least $d+1$ distinct eigenvalues.

For instance, if a graph is $d$-regular, then its largest eigenvalue is bound by d. He is connected if and only the multiplicity of d is 1.

A complete bipartite graph $K_{m,n}$ has three eigenvalues : 0, $\lambda$, $-\lambda$ where $\lambda = \sqrt{mn}$.

For more, you should check a book on algebraic graph theory like Algebraic Graph Theory, Godsile and Royle, Springer.

Note : The AM is not the "best" way to describe a graph. It's one way, very interesting in case you're looking to compute paths.

-
Actually if the graph is undirected and $d$-regular, then its largest eigenvalue is $d$ and it is also the largest eigenvalue in absolute value (and hence is the spectral radius of the adjacency matrix). –  David Kohler May 23 '11 at 23:36