Ever since the discovery of the five platonic solids in ancient times, the study of symmetry and regularity has been one of the most fascinating aspects of mathematics. Quite often the arithmetical regularity properties of an object imply its uniqueness and the existence of many symmetries. This interplay between regularity and symmetry properties of graphs is the theme of this book. Starting from very elementary regularity properties, the concept of a distance-regular graph arises naturally as a common setting for regular graphs which are extremal in one sense or another. Several other important regular combinatorial structures are then shown to be equivalent to special families of distance-regular graphs. Other subjects of more general interest, such as regularity and extremal properties in graphs, association schemes, representations of graphs in euclidean space, groups and geometries of Lie type, groups acting on graphs, and codes are covered independently. Many new results and proofs and more than 750 references increase the encyclopaedic value of this book.

Inhalt

Preface.- 1. SPECIAL REGULAR GRAPHS.- 1.1 Edge regular and co-edge-regular graphs.- 1.2 Line graphs.- 1.3 Strongly regular graphs.- Conference matrices and Paley graphs.- The Hoffman bound.- 1.4 Strongly regular graphs as extremal graphs.- 1.5 Taylor graphs and regular two-graphs.- 1.6 Square 2-designs.- 1.7 Partial ?-geometries.- A connection with affine resolvable designs.- 1.8 Hadamard matrices.- 1.9 Hadamard graphs as extremal graphs.- 1.10 Square divisible designs.- 1.11 The bipartite double of a graph.- The extended bipartite double of a graph.- 1.12 Direct products and Hamming graphs.- 1.13 d-cubes as extremal graphs.- 1.14 Gamma spaces and singular lines.- 1.15 Generalized quadrangles with line size three.- 1.16 Regular graphs without quadrangles.- 1.17 Geodetic graphs of diameter two.- 2. ASSOCIATION SCHEMES.- 2.1 Association schemes and coherent configurations.- 2.2 The Bose-Mesner algebra.- The Frame quotient.- Pseudocyclic association schemes.- 2.3 The Krein parameters.- 2.4 Imprimitivity.- Dual imprimitivity.- 2.5 Subsets in association schemes.- 2.6 Characterization of the Bose-Mesner algebra.- 2.7 Metric and cometric schemes.- The Frame quotient in a metric scheme.- 2.8 Subsets of cometric schemes; the Assmus-Mattson theorem.- 2.9 Distribution diagrams and the group case.- 2.10 Translation association schemes.- Multiplier theorems and cyclotomic schemes.- Duality.- Additive codes.- 2.11 Representation diagrams, Krein modules and spherical designs.- 3. REPRESENTATION THEORY.- 3.1 Nonnegative matrices.- 3.2 Adjacency matrices and eigenvalues of graphs.- 3.3 Interlacing.- 3.4 Gram matrices.- 3.5 Graph representations.- 3.6 The absolute bound.- 3.7 Representations of subgraphs.- 3.8 Graph switching, equiangular lines, and representations of two-graphs.- 3.9 Lattices and integral representations.- 3.10 Root systems and root lattices.- Fundamental systems and classification.- The irreducible root lattices.- Another proof of the classification.- 3.11 Graphs represented by roots of E8.- 3.12 Graphs with smallest eigenvalue at least -2.- 3.13 Equiangular lines.- 3.14 Root graphs.- Examples.- 3.15 Classification of amply regular root graphs.- Amply regular root graphs in E8.- Amply regular root graphs with ? = 2.- 4. THEORY OF DISTANCE-REGULAR GRAPHS.- 4.1 Distance-regular graphs.- Parameters.- Eigenvalues.- Eigenspaces.- Feasible parameter sets.- Imprimitivity and the Q-polynomial property.- Distance transitivity.- Distance-biregular graphs.- Weakenings of distance-regularity.- 4.2 Imprimitivity; new graphs from old.- Imprimitivity.- Parameters of halved graphs, folded graphs, and covers.- Structural conditions for the existence of covers.- Generalized Odd graphs; several P-polynomial structures.- Distance-regular line graphs.- Merging classes in distance-regular graphs.- 4.3 Substructures.- Lines.- Cubes.- Moore geometries and Petersen graphs.- 7-point biplanes.- 4.4 Representations of distance-regular graphs.- 5. PARAMETER RESTRICTIONS FOR DISTANCE-REGULAR GRAPHS.- 5.1 Unimodality of the sequence (ki)I.- 5.2 Diameter bounds by Terwilliger.- 5.3 Godsil's diameter bound. Graphs with bi = 1.- 5.4 Restrictions for ? > 1.- 5.5 Further restrictions from counting arguments.- 5.6 Graphs with small kd.- 5.7 The case $$p{dd}^2$$ = 0.- 5.8 A lower bound for $$p{dd}^{22}$$.- 5.9 Ivanov-Ivanov Theory.- 5.10 Circuit chasing.- 6. CLASSIFICATION OF THE KNOWN DISTANCE-REGULAR GRAPHS.- 6.1 Graphs with classical parameters.- 6.2 Computation of classical parameters.- 6.3 Imprimitive graphs with classical parameters; partition graphs.- 6.4 Regular near polygons.- 6.5 Generalized polygons.- 6.6 Other regular near polygons.- 6.7 Moore graphs.- 6.8 Moore geometries.- 6.9 Cages.- 6.10 The remaining primitive graphs.- 6.11 Bipartite distance-regular graphs; imprimitive regular near polygons.- 6.12 Antipodal distance-regular graphs.- 7. DISTANCE-TRANSITIVE GRAPHS.- 7.1 Some elementary group theory.- 7.2 The Thompson-Wielandt Theorem.- 7.3 A diameter bound for distance-transitive graphs.- 7.4 The case of large girth.- 7.5 Graphs with small valency.- 7.6 Imprimitive distance-transitive graphs.- 2-transitive square designs.- 2-transitive Hadamard matrices.- 2-transitive regular two-graphs.- 7.7 Towards the classification of all distance-transitive graphs.- 7.8 Further transitivity in graphs.- Distance-transitive digraphs.- Infinite distance-transitive graphs.- 8. Q-POLYNOMIAL DISTANCE-REGULAR GRAPHS.- 8.1 Leonard's characterization of Q-polynomial graphs.- Recurrence relations for Q-sequences.- Reduction of parameters.- 8.2 Imprimitive Q-polynomial distance-regular graphs.- 8.3 Further results on Q-polynomial graphs.- Q-polynomial distance-regular graphs as extremal graphs.- Explicit formulae for eigenmatrices, eigenvalues, and multiplicities.- Integrality of eigenvalues.- Bounds for girth and diameter.- 8.4 Graphs with classical parameters.- A characterization of graphs with classical parameters.- 8.5 The known Q-polynomial distance-regular graphs.- 9. THE FAMILIES OF GRAPHS WITH CLASSICAL PARAMETERS.- 9.1 Johnson graphs.- Characterizations by structure.- Characterization by parameters.- Folded Johnson graphs.- Odd graphs and doubled Odd graphs.- 9.2 Hamming graphs.- Geometric characterization.- Characterization by parameters - Pseudo Hamming graphs.- Characterization by spectrum.- Halved and folded cubes.- Covers of cubes and folded cubes - the Wells graph.- 9.3 Grassmann graphs.- Characterization by structure.- Characterization by parameters.- Graphs related to Grassmann graphs.- 9.4 Dual polar graphs.- Geometric characterization.- Characterization by parameters.- Related graphs.- 9.5 Sesquilinear forms graphs.- Bilinear forms graphs.- Alternating forms graphs.- Hermitean forms graphs.- Symmetric bilinear forms graphs.- Affine subspaces of dual polar spaces.- Antipodal covers.- 9.6 The quadratic forms graphs.- 10.GRAPHS OF COXETER AND LIE TYPE.- 10.1 Coxeter systems.- The Coxeter group as a reflection group.- The length function; reduced expressions.- The word problem in Coxeter groups.- Bruhat order.- 10.2 Coxeter graphs.- The neighbourhood of a point.- The 2-neighbourhood of a point.- Subgraphs from subdiagrams.- Objects and their shadows.- Association scheme and double coset diagram.- Product expressions for k and v.- Incidence graphs.- 10.3 The finite Coxeter graphs; root systems and presentations.- Root systems.- 10.4 Global properties.- Finiteness.- Diameter and permutation rank.- Amply regular Coxeter graphs.- Distance-regular Coxeter graphs.- Multiplicity-free representations.- 10.5 Tits Systems.- The association scheme of a Tits system.- Nonexistence results.- 10.6 Graphs of Lie Type.- Subgraphs from subdiagrams.- Objects.- Lines.- Singular lines.- Transitivity properties.- Relation between a graph of Lie type and the associated Coxeter graph.- Incidence graphs.- 10.7 Cheval…