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 images will be denoted imagesm×n, i.e. m (respectively, n) is the number of rows (respectively, columns). The transpose of the matrix M will be denoted by M

Get Advanced Graph Theory and Combinatorics now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.