Distance-regular graphs. (English) Zbl 0747.05073

Brouwer, Andries E.; Cohen, Arjeh M.; Neumaier, Arnold

Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge, 18. Berlin etc.: Springer-Verlag. xvii, 495 p. (1989).

Let \(\Gamma\) be a connected graph, and denote by \(\Gamma_ i(x)\) the set of vertices of \(\Gamma\) which are at distance \(i\) from vertex \(x\). If, for vertices \(x\) and \(y\) with \(y\in\Gamma_ i(x)\), the numbers \(a_ i=|\Gamma_ i(x)\cap\Gamma_ 1(y)|\), \(b_ i=|\Gamma_{i+1}(x)\cap\Gamma_ 1(y)|\), \(c_ i=|\Gamma_{i-1}(x)\cap\Gamma_ 1(y)|\) do not in fact depend on \(x\) and \(y\), but only on \(i\), then \(\Gamma\) is called a distance-regular graph.
Distance-regular graphs arise naturally in a number of contexts. There are connections to coding theory, design theory, geometry and group theory, as well as to other areas of graph theory. As a result, this has been an active area of research for the last 15-20 years.
This book has two parts: The first develops the theory of distance- regular graphs, while the second is devoted to the description and classification of the known distance-regular graphs. From the preface: “The main emphasis of this book is on describing the known distance- regular graphs, on classifying and, if possible, characterizing them. The structure of these graphs is touched upon insofar as necessary to describe the graphs, determine their intersection arrays, or characterize them.” Also included are tables of parameters for distance-regular graphs, and an extensive bibliography.
This well-written work is the only book devoted entirely to distance- regular graphs. It does not attempt to develop extensively the theory of association schemes, however, since this is done in E. Bannai and T. Ito’s book [Algebraic combinatorics. I: Association schemes. Mathematics Lecture Note Series, Menlo Park, California etc.: The Benjamin/Cummings Publishing Company, Inc. Advanced Book Program. XXIV, 425 p. (1984; Zbl 0555.05019)]. It also concentrates on graphs with diameter at least three, not attempting to survey the extensive theory of strongly regular graphs.

MSC:

05C75	Structural characterization of families of graphs
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics

Keywords:

distance-regular graphs; classification; intersection arrays

Citations:

Zbl 0555.05019