ALGEBRAIC GRAPH THEORYPDF电子书下载

1 Graphs 1

1.1 Graphs 1

1.2 Subgraphs 3

1.3 Automorphisms 4

1.4 Homomorphisms 6

1.5 Circulant Graphs 8

1.6 Johnson Graphs 9

1.7 Line Graphs 10

1.8 Planar Graphs 12

Exercises 16

Notes 17

References 18

2 Groups 19

2.1 Permutation Groups 19

2.2 Counting 20

2.3 Asymmetric Graphs 22

2.4 Orbits on Pairs 25

2.5 Primitivity 27

2.6 Primitivity and Connectivity 29

Exercises 30

Notes 32

References 32

3 Trnnsitive Graphs 33

3.1 Vertex-Transitive Graphs 33

3.2 Edge-Transitive Graphs 35

3.3 Edge Connectivity 37

3.4 Vertex Connectivity 39

3.5 Matchings 43

3.6 Hamilton Paths and Cycles 45

3.7 Cayley Graphs 47

3.8 Directed Cayley Graphs with No Hamilton Cycles 49

3.9 Retracts 51

3.10 Transpositions 52

Exercises 54

Notes 56

References 57

4 Arc-Transitive Graphs 59

4.1 Arc-Transitive Graphs 59

4.2 Arc Graphs 61

4.3 Cubic Arc-Transitive Graphs 63

4.4 The Petersen Graph 64

4.5 Distance-Transitive Graphs 66

4.6 The Coxeter Graph 69

4.7 Tutte’s 8-Cage 71

Exercises 74

Notes 76

References 76

5 Generalized Polygons and Moore Graphs 77

5.1 Incidence Graphs 78

5.2 Projective Planes 79

5.3 A Family of Projective Planes 80

5.4 Generalized Quadrangles 81

5.5 A Family of Generalized Quadrangles 83

5.6 Generalized Polygons 84

5.7 Two Generalized Hexagons 88

5.8 Moore Graphs 90

5.9 The Hoffman-Singleton Graph 92

5.10 Designs 94

Exercises 97

Notes 100

References 100

6 Homomorphisms 103

6.1 The Basics 103

6.2 Cores 104

6.3 Products 106

6.4 The Map Graph 108

6.5 Counting Homomorphisms 109

6.6 Products and Colourings 110

6.7 Uniquely Colourable Graphs 113

6.8 Foldings and Covers 114

6.9 Cores with No Triangles 116

6.10 The Andrasfai Graphs 118

6.11 Colouring Andrasfai Graphs 119

6.12 A Characterization 121

6.13 Cores of Vertex-Transitive Graphs 123

6.14 Cores of Cubic Vertex-Transitive Graphs 125

Exercises 128

Notes 132

References 133

7 Kneser Graphs 135

7.1 Fractional Colourings and Cliques 135

7.2 Fractional Cliques 136

7.3 Fractional Chromatic Number 137

7.4 Homomorphisms and Fractional Colourings 138

7.5 Duality 141

7.6 Imperfect Graphs 142

7.7 Cyclic Interval Graphs 145

7.8 Erdos-Ko-Rado 146

7.9 Homomorphisms of Kneser Graphs 148

7.10 Induced Homomorphisms 149

7.11 The Chromatic Number of the Kneser Graph 150

7.12 Gale’s Theorem 152

7.13 Welzl’s Theorem 153

7.14 The Cartesian Product 154

7.15 Strong Products and Colourings 155

Exercises 156

Notes 159

References 160

8 Matrix Theory 163

8.1 The Adjacency Matrix 163

8.2 The Incidence Matrix 165

8.3 The Incidence Matrix of an Oriented Graph 167

8.4 Symmetric Matrices 169

8.5 Eigenvectors 171

8.6 Positive Semidefinite Matrices 173

8.7 Subharmonic Functions 175

8.8 The Perron-Frobenius Theorem 178

8.9 The Rank of a Symmetric Matrix 179

8.10 The Binary Rank of the Adjacency Matrix 181

8.11 The Symplectic Graphs 183

8.12 Speetral Decomposition 185

8.13 Ratlonal Functions 187

Exercises 188

Notes 192

References 192

9 Interlacing 193

9.1 Interlacing 193

9.2 Inside and Outside the Petersen Graph 195

9.3 Equitable Partitions 195

9.4 Eigenvalues of Kneser Graphs 199

9.5 More Interlacing 202

9.6 More Applications 203

9.7 Bipartite Subgraphs 206

9.8 Fullerenes 208

9.9 Stability of Fullerenes 210

Exercises 213

Notes 215

References 216

10 Strongly Regular Graphs 217

10.1 Parameters 218

10.2 Eigenvalues 219

10.3 Some Characterizations 221

10.4 Latin Square Graphs 223

10.5 Small Strongly Regular Graphs 226

10.6 Local Eigenvalues 227

10.7 The Krein Bounds 231

10.8 Generalized Quadrangles 235

10.9 Lines of Size Three 237

10.10 Quasi-Symmetric Designs 239

10.11 The Witt Design on 23 Points 241

10.12 The Symplectic Graphs 242

Exercises 244

Notes 246

References 247

11 Two-Graphs 249

11.1 Equiangular Lines 249

11.2 The Absolute Bound 251

11.3 Tightness 252

11.4 The Relative Bound 253

11.5 Switching 254

11.6 Regular Two-Graphs 256

11.7 Switching and Strongly Regular Graphs 258

11.8 The Two-Graph on 276 Vertices 262

Exercises 263

Notes 263

References 265

12 Line Graphs and Eigenvalues 265

12.1 Generalized Line Graphs 266

12.2 Star-Closed Sets of Lines 267

12.3 Reflections 268

12.4 Indecomposable Star-Closed Sets 270

12.5 A Generating Set 271

12.6 The Classification 272

12.7 Root Systems 274

12.8 Consequences 276

12.9 A Strongly Regular Graph 277

Exercises 278

Notes 278

References 279

13 The Laplacian of a Graph 279

13.1 The Laplacian Matrix 281

13.2 Trees 284

13.3 Representations 287

13.4 Energy and Eigenvalues 288

13.5 Connectivity 290

13.6 Interlacing 292

13.7 Conductance and Cutsets 293

13.8 How to Draw a Graph 295

13.9 The Generalized Laplacian 298

13.10 Multiplicities 300

13.11 Embeddings 302

Exercises 305

Notes 306

References 307

14 Cuts and Flows 308

14.1 The Cut Space 310

14.2 The Flow Space 312

14.3 Planar Graphs 313

14.4 Bases and Ear Decompositions 315

14.5 Lattices 316

14.6 Duality 317

14.7 Integer Cuts and Flows 319

14.8 Projections and Duals 321

14.9 Chip Firing 323

14.10 Two Bounds 324

14.11 Recurrent States 325

14.12 Critical States 326

14.13 The Critical Group 327

14.14 Voronoi Polyhedra 329

14.15 Bicycles 332

14.16 The Principal Tripartition 334

Exercises 336

Notes 338

References 338

15 The Rank Polynomial 341

15.1 Rank Functions 341

15.2 Matroids 343

15.3 Duality 344

15.4 Restriction and Contraction 346

15.5 Codes 347

15.6 The Deletion-Contraction Algorithm 349

15.7 Bicycles in Binary Codes 351

15.8 Two Graph Polynomials 353

15.9 Rank Polynomial 355

15.10 Evaluations of the Rank Polynomial 357

15.11 The Weight Enumerator of a Code 358

15.12 Colourings and Codes 359

15.13 Signed Matroids 361

15.14 Rotors 363

15.15 Submodular Functions 366

Exercises 369

Notes 371

References 372

16 Knots 373

16.1 Knots and Their Projections 374

16.2 Reidemeister Moves 376

16.3 Signed Plane Graphs 379

16.4 Reidemeister moves on graphs 381

16.5 Reidemeister Invariants 383

16.6 The Kauffman Bracket 385

16.7 The Jones Polynomial 386

16.8 Connectivity 388

Exercises 391

Notes 392

References 392

17 Knots and Eulerian Cycles 395

17.1 Eulerian Partitions and Tours 395

17.2 The Medial Graph 398

17.3 Link Components and Bicycles 400

17.4 Gauss Codes 403

17.5 Chords and Circles 405

17.6 Flipping Words 407

17.7 Characterizing Gauss Codes 408

17.8 Bent Tours and Spanning Trees 410

17.9 Bent Partitions and the Rank Polynomial 413

17.10 Maps 414

17.11 Orientable Maps 417

17.12 Seifert Circles 419

17.13 Seifert Circles and Rank 420

Exercises 423

Notes 424

References 425

Glossary of Symbols 427

Index 433