ALGEBRAIC GRAPH THEORYPDF|Epub|txt|kindle电子书版本网盘下载

ALGEBRAIC GRAPH THEORYPDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1 Graphs1

1.1 Graphs1

1.2 Subgraphs3

1.3 Automorphisms4

1.4 Homomorphisms6

1.5 Circulant Graphs8

1.6 Johnson Graphs9

1.7 Line Graphs10

1.8 Planar Graphs12

Exercises16

Notes17

References18

2 Groups19

2.1 Permutation Groups19

2.2 Counting20

2.3 Asymmetric Graphs22

2.4 Orbits on Pairs25

2.5 Primitivity27

2.6 Primitivity and Connectivity29

Exercises30

Notes32

References32

3 Trnnsitive Graphs33

3.1 Vertex-Transitive Graphs33

3.2 Edge-Transitive Graphs35

3.3 Edge Connectivity37

3.4 Vertex Connectivity39

3.5 Matchings43

3.6 Hamilton Paths and Cycles45

3.7 Cayley Graphs47

3.8 Directed Cayley Graphs with No Hamilton Cycles49

3.9 Retracts51

3.10 Transpositions52

Exercises54

Notes56

References57

4 Arc-Transitive Graphs59

4.1 Arc-Transitive Graphs59

4.2 Arc Graphs61

4.3 Cubic Arc-Transitive Graphs63

4.4 The Petersen Graph64

4.5 Distance-Transitive Graphs66

4.6 The Coxeter Graph69

4.7 Tutte’s 8-Cage71

Exercises74

Notes76

References76

5 Generalized Polygons and Moore Graphs77

5.1 Incidence Graphs78

5.2 Projective Planes79

5.3 A Family of Projective Planes80

5.4 Generalized Quadrangles81

5.5 A Family of Generalized Quadrangles83

5.6 Generalized Polygons84

5.7 Two Generalized Hexagons88

5.8 Moore Graphs90

5.9 The Hoffman-Singleton Graph92

5.10 Designs94

Exercises97

Notes100

References100

6 Homomorphisms103

6.1 The Basics103

6.2 Cores104

6.3 Products106

6.4 The Map Graph108

6.5 Counting Homomorphisms109

6.6 Products and Colourings110

6.7 Uniquely Colourable Graphs113

6.8 Foldings and Covers114

6.9 Cores with No Triangles116

6.10 The Andrasfai Graphs118

6.11 Colouring Andrasfai Graphs119

6.12 A Characterization121

6.13 Cores of Vertex-Transitive Graphs123

6.14 Cores of Cubic Vertex-Transitive Graphs125

Exercises128

Notes132

References133

7 Kneser Graphs135

7.1 Fractional Colourings and Cliques135

7.2 Fractional Cliques136

7.3 Fractional Chromatic Number137

7.4 Homomorphisms and Fractional Colourings138

7.5 Duality141

7.6 Imperfect Graphs142

7.7 Cyclic Interval Graphs145

7.8 Erdos-Ko-Rado146

7.9 Homomorphisms of Kneser Graphs148

7.10 Induced Homomorphisms149

7.11 The Chromatic Number of the Kneser Graph150

7.12 Gale’s Theorem152

7.13 Welzl’s Theorem153

7.14 The Cartesian Product154

7.15 Strong Products and Colourings155

Exercises156

Notes159

References160

8 Matrix Theory163

8.1 The Adjacency Matrix163

8.2 The Incidence Matrix165

8.3 The Incidence Matrix of an Oriented Graph167

8.4 Symmetric Matrices169

8.5 Eigenvectors171

8.6 Positive Semidefinite Matrices173

8.7 Subharmonic Functions175

8.8 The Perron-Frobenius Theorem178

8.9 The Rank of a Symmetric Matrix179

8.10 The Binary Rank of the Adjacency Matrix181

8.11 The Symplectic Graphs183

8.12 Speetral Decomposition185

8.13 Ratlonal Functions187

Exercises188

Notes192

References192

9 Interlacing193

9.1 Interlacing193

9.2 Inside and Outside the Petersen Graph195

9.3 Equitable Partitions195

9.4 Eigenvalues of Kneser Graphs199

9.5 More Interlacing202

9.6 More Applications203

9.7 Bipartite Subgraphs206

9.8 Fullerenes208

9.9 Stability of Fullerenes210

Exercises213

Notes215

References216

10 Strongly Regular Graphs217

10.1 Parameters218

10.2 Eigenvalues219

10.3 Some Characterizations221

10.4 Latin Square Graphs223

10.5 Small Strongly Regular Graphs226

10.6 Local Eigenvalues227

10.7 The Krein Bounds231

10.8 Generalized Quadrangles235

10.9 Lines of Size Three237

10.10 Quasi-Symmetric Designs239

10.11 The Witt Design on 23 Points241

10.12 The Symplectic Graphs242

Exercises244

Notes246

References247

11 Two-Graphs249

11.1 Equiangular Lines249

11.2 The Absolute Bound251

11.3 Tightness252

11.4 The Relative Bound253

11.5 Switching254

11.6 Regular Two-Graphs256

11.7 Switching and Strongly Regular Graphs258

11.8 The Two-Graph on 276 Vertices262

Exercises263

Notes263

References265

12 Line Graphs and Eigenvalues265

12.1 Generalized Line Graphs266

12.2 Star-Closed Sets of Lines267

12.3 Reflections268

12.4 Indecomposable Star-Closed Sets270

12.5 A Generating Set271

12.6 The Classification272

12.7 Root Systems274

12.8 Consequences276

12.9 A Strongly Regular Graph277

Exercises278

Notes278

References279

13 The Laplacian of a Graph279

13.1 The Laplacian Matrix281

13.2 Trees284

13.3 Representations287

13.4 Energy and Eigenvalues288

13.5 Connectivity290

13.6 Interlacing292

13.7 Conductance and Cutsets293

13.8 How to Draw a Graph295

13.9 The Generalized Laplacian298

13.10 Multiplicities300

13.11 Embeddings302

Exercises305

Notes306

References307

14 Cuts and Flows308

14.1 The Cut Space310

14.2 The Flow Space312

14.3 Planar Graphs313

14.4 Bases and Ear Decompositions315

14.5 Lattices316

14.6 Duality317

14.7 Integer Cuts and Flows319

14.8 Projections and Duals321

14.9 Chip Firing323

14.10 Two Bounds324

14.11 Recurrent States325

14.12 Critical States326

14.13 The Critical Group327

14.14 Voronoi Polyhedra329

14.15 Bicycles332

14.16 The Principal Tripartition334

Exercises336

Notes338

References338

15 The Rank Polynomial341

15.1 Rank Functions341

15.2 Matroids343

15.3 Duality344

15.4 Restriction and Contraction346

15.5 Codes347

15.6 The Deletion-Contraction Algorithm349

15.7 Bicycles in Binary Codes351

15.8 Two Graph Polynomials353

15.9 Rank Polynomial355

15.10 Evaluations of the Rank Polynomial357

15.11 The Weight Enumerator of a Code358

15.12 Colourings and Codes359

15.13 Signed Matroids361

15.14 Rotors363

15.15 Submodular Functions366

Exercises369

Notes371

References372

16 Knots373

16.1 Knots and Their Projections374

16.2 Reidemeister Moves376

16.3 Signed Plane Graphs379

16.4 Reidemeister moves on graphs381

16.5 Reidemeister Invariants383

16.6 The Kauffman Bracket385

16.7 The Jones Polynomial386

16.8 Connectivity388

Exercises391

Notes392

References392

17 Knots and Eulerian Cycles395

17.1 Eulerian Partitions and Tours395

17.2 The Medial Graph398

17.3 Link Components and Bicycles400

17.4 Gauss Codes403

17.5 Chords and Circles405

17.6 Flipping Words407

17.7 Characterizing Gauss Codes408

17.8 Bent Tours and Spanning Trees410

17.9 Bent Partitions and the Rank Polynomial413

17.10 Maps414

17.11 Orientable Maps417

17.12 Seifert Circles419

17.13 Seifert Circles and Rank420

Exercises423

Notes424

References425

Glossary of Symbols427

Index433