Author | Brouwer, Andries E. author |
---|---|
Title | Distance-Regular Graphs [electronic resource] / by Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier |
Imprint | Berlin, Heidelberg : Springer Berlin Heidelberg, 1989 |
Connect to | http://dx.doi.org/10.1007/978-3-642-74341-2 |
Descript | XVII, 495 p. online resource |
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