Algebraic graph theory. (English) Zbl 0968.05002

Godsil, Chris; Royle, Gordon

Graduate Texts in Mathematics. 207. New York, NY: Springer. xix, 439 p. (2001).

Although there are several standard methods that are used in graph theory, e.g. double counting, many of its results depend on ad hoc arguments. Students often get the impression that the proof of every theorem requires new ingenuity. The purpose of this book on algebraic graph theory is to show many unexpected and useful applications of algebraic methods to derive results in graph theory. Some of these methods are from group theory. The most notable methods are from matrix theory; especially the eigenvalue techniques have proved to be important. The concepts that are treated are Moore graphs, generalized polygons, strongly regular graphs and distance regular graphs, two-graphs and furthermore a large number of concepts originating from research papers that appeared in the past two decades. This implies that a researcher in graph theory will not only find a number of familiar techniques in this book but quite likely many theorems that he has not seen before. Each chapter ends with a large number of exercises, often proofs of theorems that are left to the reader. Several teachers of courses in this area will be happy to see that no hints or solutions are provided. In the preface, the authors state that the book could even be used for a first course in graph theory. This reviewer does not share that opinion. However, for a graduate course the book is very suitable. It is mostly self-contained but the reader should know linear algebra and some group theory. (At one point the reader is apparently supposed to know what the classification of finite simple groups is.) For a number of the theorems, but not all, the notes provide the source. The first four chapters contain mostly introductory material. The authors define a graph as having no loops (a word that is used before it is defined) except in one chapter. Automorphisms and homomorphisms of graphs are treated (also in Chapter 6), permutation groups, and (both vertex- and arc-)transitive graphs. In these chapters, several classes of graphs are introduced in order to have examples to illustrate the theorems: circulant graphs, Johnson graphs, Cayley graphs and also the Petersen graph, Tutte’s 8-cage, the Coxeter graph and the Hoffman-Singleton graph. Particular attention is paid to the Kneser graphs which appear in many chapters. These chapters also contain material from the non-algebraic part of graph theory such as Euler’s formula, Menger’s theorem , and theorems about Hamilton cycles. In Chapter 5, generalized polygons and Moore graphs are treated. (It is somewhat confusing that the authors apparently exclude \(n\)-gons, except the pentagon.) In Chapter 7 on Kneser graphs the concepts fractional colourings, fractional cliques and fractional chromatic number are introduced. Applying some of the results to Kneser graphs provides a proof of the Erdős-Ko-Rado theorem. After another introductory chapter on matrix theory, including Perron-Frobenius, comes the nicest part of algebraic graph theory. The remarkably strong method of interlacing of eigenvalues and equitable partitions are treated and applied to study fullerenes, a special type of carbon molecules. One of the best known impressive applications of algebraic methods in graph theory is the theory of strongly regular graphs. This is presented in Chapter 10. In the reviewer’s opinion, this chapter could have been considerably longer. Two quite elegant generalizations of strongly regular graphs, namely neighbourhood regular graphs (due to the first author and B. D. McKay [Combinatorial mathematics VII, Lect. Notes Math. 829, 127-140 (1980; Zbl 0453.05052)]) and directed strongly regular graphs (A. M. Duval [J. Comb. Theory, Ser. A 47, No. 1, 71-100 (1988; Zbl 0642.05025)]) are not included. Chapter 11 on two-graphs is partly based on several papers by J. J. Seidel [cf. Geometry and combinatorics (Academic Press, Boston) (1991; Zbl 0770.05001)]. A fundamental paper by P. J. Cameron, J. M. Goethals, J. J. Seidel, and E. E. Shult [J. Algebra 43, 305-327 (1976; Zbl 0337.05142)] is the source for Chapter 12 on line graphs and eigenvalues. The most common matrices that are used to describe graphs and subsequently use algebraic methods to prove theorems on graphs are the adjacency matrix and the incidence matrix. Less familiar is the concept of the Laplacian of a graph. This is introduced in Chapter 13, a chapter in which nearly all the results are less than ten years old. Chapter 14 starts with the familiar concepts of cut space and flow space of a graph and planarity. This is followed by lattices and a game on a graph called “chip-firing”, introduced by A. Björner, L. Lovász, and P. W. Shor [Eur. J. Comb. 12, No. 4, 283-291 (1991; Zbl 0729.05048)]. The last three chapters are devoted to the connection between graph theory and knot theory. To show the connection between the rank polynomial of a graph and the so-called Jones polynomial, methods from matroid theory are treated first.
This book is well written. The subjects that the authors have treated, respectively left out, obviously depend on their own taste. Similarly, the opinion of a reviewer is personal. In this case, that opinion is that algebraic graph theory is a much more suitable topic to teach (say in a graduate course) than several unstructured parts of graph theory. Therefore, especially the first half of this book is quite useful as a text for courses. For a researcher in the field, the book is a must!

Reviewer: J.H.van Lint (Eindhoven)

MSC:

05-02	Research exposition (monographs, survey articles) pertaining to combinatorics
05Cxx	Graph theory
05Exx	Algebraic combinatorics

Keywords:

distance regular graphs; matrix theory; eigenvalue techniques; Moore graphs; generalized polygons; strongly regular graphs; Kneser graphs; Menger’s theorem; colourings; Erdős-Ko-Rado theorem; fullerences

Citations:

Zbl 0453.05052; Zbl 0337.05142; Zbl 0729.05048; Zbl 0770.05001; Zbl 0642.05025