Handbook of Linear Algebra, 2nd Edition

Chapter 39

Matrices and Graphs

Willem H. Haemers

Tilburg University

The first two sections of this chapter give a short introduction to graph theory. Unfortunately much graph theoretic terminology is not standard, so we had to choose. We allow, for example, graphs to have multiple edges and loops, and call a graph simple if it has none of these. On the other hand, we assume that graphs are finite.

For all nontrivial facts, references are given, sometimes to the original source, but often to textbooks or survey papers. A recent global reference for this chapter is [BH12].

39.1 Graphs: Basic Notions

Definitions:

A graph G = (V, E) consists of a finite set V = {v1,..., vn} of vertices and a finite multiset E of edges, where each edge is a pair { ...