Topics in Algebraic Graph Theory

Cover......Page 1
About......Page 2
ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS 102......Page 4
Topics in Algebraic Graph Theory......Page 6
Copyright - ISBN: 9780521801973......Page 7
Contents......Page 8
Preface......Page 12
Foreword......Page 14
1. Graph theory......Page 18
2. Linear algebra......Page 27
3. Group theory......Page 36
1. Introduction......Page 47
2. Some examples......Page 48
3. A little matrix theory......Page 50
4. Eigenvalues and walks......Page 51
5. Eigenvalues and labellings of graphs......Page 56
6. Lower bounds for the eigenvalues......Page 60
7. Upper bounds for the eigenvalues......Page 64
8. Other matrices related to graphs......Page 67
9. Cospectral graphs......Page 68
1. Introduction......Page 73
2. Some classical theorems......Page 75
3. Digraphs......Page 78
4. Biclique partitions of graphs......Page 84
5. Bipartite graphs......Page 86
6. Permanents......Page 89
7. Converting the permanent into the determinant......Page 92
8. Chordal graphs and perfect Gaussian elimination......Page 96
9. Ranking players in tournaments......Page 99
1. Introduction......Page 105
2. Angles......Page 106
3. Star sets and star partitions......Page 111
4. Star complements......Page 113
5. Exceptional graphs......Page 116
6. Reconstructing the characteristic polynomial......Page 118
7. Non-complete extended p-sums of graphs......Page 121
8. Integral graphs......Page 124
1. Introduction......Page 130
2. The Laplacian of a graph......Page 132
3. Laplace eigenvalues......Page 134
4. Eigenvalues and vertex partitions of graphs......Page 139
5. The max-cut problem and semi-definite programming......Page 142
6. Isoperimetric inequalities......Page 144
7. The travelling salesman problem......Page 146
8. Random walks on graphs......Page 147
1. Graph automorphisms......Page 154
2. Algorithmic aspects......Page 156
3. Automorphisms of typical graphs......Page 157
4. Permutation groups......Page 158
5. Abstract groups......Page 159
6. Cayley graphs......Page 161
7. Vertex-transitive graphs......Page 162
8. Higher symmetry......Page 165
9. Infinite graphs......Page 166
10. Graph homomorphisms......Page 169
1. Introduction......Page 173
2. Recognition......Page 174
3. Special examples......Page 176
4. Prevalence......Page 177
5. Isomorphism......Page 181
6. Enumeration......Page 184
7. Automorphisms......Page 185
8. Subgraphs......Page 186
9. Hamiltonicity......Page 188
10. Factorization......Page 190
11. Embeddings......Page 191
12. Applications......Page 192
1. Introduction......Page 196
2. s-arc transitive graphs......Page 198
3. Group-theoretic constructions......Page 199
4. Quotient graphs and primitivity......Page 203
5. Distance-transitive graphs......Page 204
6. Local characterizations......Page 206
7. Normal quotients......Page 209
8. Finding automorphism groups......Page 213
9. A geometric approach......Page 215
10. Related families of graphs......Page 216
1. An example......Page 220
2. Regularity conditions......Page 222
3. Parameter conditions......Page 223
4. Geometric graphs......Page 225
5. Eigenvalues and their geometry......Page 229
6. Rank 3 graphs......Page 231
7. Related classes of graphs......Page 234
1. Introduction......Page 239
2. Distance-transitivity......Page 240
3. Graphs from groups......Page 243
4. Combinatorial properties......Page 247
5. Imprimitivity......Page 250
6. Bounds......Page 252
7. Finite simple groups......Page 253
8. The first step......Page 255
9. The affine case......Page 257
10. The simple socle case......Page 262
1. Introduction......Page 267
2. Permutation group algorithms......Page 268
3. Storing and accessing a G-graph......Page 270
4. Constructing G-graphs......Page 271
5. G-breadth-first search in a G-graph......Page 272
6. Automorphism groups and graph isomorphism......Page 274
7. Computing with vertex-transitive graphs......Page 276
8. Coset enumeration......Page 278
9. Coset enumeration for symmetric graphs......Page 279
Notes on contributors......Page 284
Index of definitions......Page 288