Distance-Regular Graphs

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.

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 Chevalley Groups.- Graphs of Lie Type from Chevalley groups.- Parameters.- Computation of the parameters of E7,7(q) - geometric approach.- 10.8 The affine E6 graph.- 10.9 Distance-transitive representations of Chevalley groups.- 11. GRAPHS RELATED TO CODES.- 11.1 Completely regular codes.- Codes in distance-regular graphs.- Completely regular partitions and distance-regular quotient graphs.- Distance-regular graphs with regular abelian automorphism groups.- Completely regular codes in the Hamming scheme.- Completely regular codes in other distance-regular graphs.- 11.2 Graphs from the Kasami codes.- 11.3 Graphs from the Golay codes.- The coset graph of the extended ternary Golay code.- The coset graph of the ternary Golay code.- The coset graph of the truncated ternary Golay code.- The coset graph of the extended binary Golay code.- The coset graph of the binary Golay code.- The coset graph of the truncated binary Golay code.- The coset graph of the doubly truncated binary Golay code and the graph of the unitals in PG(2,4).- Variations on the theme of coset graph - some antipodal covers.- 11.4 Graphs related to the Witt designs.- The Witt graph associated to M24.- The truncated Witt graph associated to M23.- The doubly truncated Witt graph associated to M22.- The Ivanov-Ivanov-Faradjev graph.- Higman’s symmetric design.- The Leonard graph - M12.2 over PGL(2,11).- The Hadamard association scheme.- Antipodal 2-covers of the Gewirtz graph.- The regular two-graph on 276 vertices and the McLaughlin graph.- 11.5 The van Lint-Schrijver partial geometry.- 12. GRAPHS RELATED TO CLASSICAL GEOMETRIES.- 12.1 The even orthogonal case; the Doro graph.- 12.2 The odd orthogonal case.- 12.3 The Coxeter graph for PSL(2,7).- 12.4 The unitary case.- 12.5 Antipodal covers of complete graphs.- 12.6 Thin near octagons from Denniston’s complete arcs.- 12.7 Antipodal covers of complete graphs from pseudocyclic association schemes.- Cyclotomic schemes.- The Mathon and Hollmann schemes on 28 points, and conics in PG(2,q).- The Hollmann scheme on 496 points.- 13. SPORADIC GRAPHS.- 13.1 Graphs related to the Hoffman - Singleton graph.- Sylvester’s double six graph.- 13.2 Commuting involutions graphs and Fischer spaces.- Five antipodal 3-covers.- The Foster graph for 3·Sym(6).2 and the hexacode.- The Conway-Smith graph for 3·Sym(7).- The locally GQ(4,2) graph on 3×126 points.- The 3.O7,(3) graph on 3×378 points.- 13.3 The Perkel graph for L(2, 19).- 13.4 The Biggs-Smith graph for L(2, 17).- 13.5 The Livingstone graph for J1.- 13.6 The near octagon associated with the Hall-Janko group.- 13.7 The Patterson graph for Suz.- 14. TABLES OF PARAMETERS FOR DISTANCE REGULAR GRAPHS.- A. APPEND.- A.1 Graphs.- A.2 Permutation groups.- A.3 Automorphisms.- A.4 Regular partitions, distribution diagrams and double coset graphs.- A.5 Primitivity.- A.6 Designs.- A.7 Codes.- A.8 Singular subspaces.- A.9 Geometries.- A.10 Miscellaneous notation.- References.- Symbols and notation.- Intersection arrays.- Author index.