Distance-Regular Graphs

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.