Advanced Graph Theory and Combinatorics

8Algebraic Graph Theory

We are at a turning point of the book. In this chapter, we will discover that associating a matrix with a graph is a powerful concept because we can make use of all the machinery of linear algebra and matrix computations. In the following chapter, we will see that if the associated matrix has special properties (primitivity or irreducibility) then much more can be said about the corresponding graph. In particular, for Google’s PageRank (see Chapter 10), one of the key points is to modify a graph to obtain a primitive matrix. For instance, we will soon learn the fact that a graph is bipartite is completely characterized by its spectrum, i.e. the set of eigenvalues of the associated matrix, or that the first coefficients of its characteristic polynomial have a combinatorial interpretation.

8.1. Prerequisites

We assume that the reader has a working knowledge of linear algebra. In this section, we fix notation and recap a few classical results that can be found in any textbook. In particular, matrices and row or column vectors will be denoted using boldface fonts. The set of m × n matrices with entries in the ring will be denoted ^m×n, i.e. m (respectively, n) is the number of rows (respectively, columns). The transpose of the matrix M will be denoted by M