代数图论

本书面向图论、组合数 学和离散数学领域的研究生 及研究人员，主要论述代数 与图论之间的关系，阅读本 书只需具备线性代数及群论 方面的基础知识，因此本书 也适用于高年级本科生。目 次：图；群；传递图；反传 递图；广义多项式和穆尔图 ；克内泽尔图；矩阵理论； 交错；强正则图；二图；线 图和本征值；图的拉普拉斯 算子；切割与流量；秩多项 式；纽结；纽结和欧拉循环 。读者对象：数学专业的研 究生及高年级本科生。

Preface 1 Graphs 1.1 Graphs 1.2 Subgraphs 1.3 Automorphisms 1.4 Homomorphisms 1.5 Circulant Graphs 1.6 Johnson Graphs 1.7 Line Graphs 1.8 Planar Graphs Exercises Notes References 2 Groups 2.1 Permutation Groups 2.2 Counting 2.3 Asymmetric Graphs 2.4 Orbits on Pairs 2.5 Primitivity 2.6 Primitivity and Connectivity Exercises Notes References 3 Transitive Graphs 3.1 Vertex-Transitive Graphs 3.2 Edge-Transitive Graphs 3.3 Edge Connectivity 3.4 Vertex Connectivity 3.5 Matchings 3.6 Hamilton Paths and Cycles 3.7 Cayley Graphs 3.8 Directed Cayley Graphs with No Hamilton Cycles 3.9 Retracts 3.10 Transpositions Exercises Notes References 4 Arc-Transitive Graphs 4.1 Arc-Transitive Graphs 4.2 Arc Graphs 4.3 Cubic Arc-Transitive Graphs 4.4 The Petersen Graph 4.5 Distance-Transitive Graphs 4.6 The Coxeter Graph 4.7 Tutte's 8-Cage Exercises Notes References 5 Generalized Polygons and Moore Graphs 5.1 Incidence Graphs 5.2 Projective Planes 5.3 A Family of Projective Planes 5.4 Generalized Quadrangles 5.5 A Family of Generalized Quadrangles 5.6 Generalized Polygons 5.7 Two Generalized Hexagons 5.8 Moore Graphs 5.9 The Hoffman-Singleton Graph 5.10 Designs Exercises Notes References 6 Homomorphisms 6.1 The Basics 6.2 Cores 6.3 Products …… 7 Kneser Graphs 8 Matrix Theory 9 Interlacing 10 Strongly Regular Graphs 11 Two-Graphs 12 Line Graphs and Eigenvalues 13 The Laplacian of a Graph 14 Cuts and Flows 15 The Rank Polynomial 16 Knots 17 Knots and Eulerian Cycles Glossary of Symbols Index