The spectrum of a graph

Let $\Gamma$ be a finite graph (directed or not). We can associate a matrix $A$, called the adjacency matrix of $\Gamma$ to this graph, by letting $A$ be a 0-1 matrix indexed by the vertex set of $\Gamma$, where $A_{xy} = 1$ if and only if there is an edge from $x$ to $y$ in $\Gamma$. The spectrum of the graph $\Gamma$ is by definition the spectrum of the matrix $A$. This is certainly the right choice when $\Gamma$ is regular; for not necessarily regular graphs the matrix $L$ with zero row sums defined by $L_{xy} = - A_{xy}$ for $x \ne y$ is also a useful tool. It is known as `the discrete Laplace operator'.

We want to connect graph properties to properties of the spectrum of $A$ (or $L$).

First some graph terminology, linear algebra, and Perron-Frobenius theory.