Algebraic Graph Theory (eBook)

lt;!doctype html public "-//w3c//dtd html 4.0 transitional//en">

Ulrich Knauer, Carl von Ossietzky Universität Oldenburg, Germany.

Preface 6
Contents 12
1 Directed and undirected graphs 18
1.1 Formal description of graphs 18
1.2 Connectedness and equivalence relations 21
1.3 Some special graphs 22
1.4 Homomorphisms 24
1.5 Half-, locally, quasi-strong and metric homomorphisms 28
1.6 The factor graph, congruences, and the Homomorphism Theorem 31
Factor graphs 31
The Homomorphism Theorem 32
1.7 The endomorphism type of a graph 35
1.8 Comments 41
2 Graphs and matrices 43
2.1 Adjacency matrix 43
Isomorphic graphs and the adjacency matrix 45
Components and the adjacency matrix 46
Adjacency list 47
2.2 Incidence matrix 47
2.3 Distances in graphs 48
The adjacency matrix and paths 49
The adjacency matrix, the distance matrix and circuits 50
2.4 Endomorphisms and commuting graphs 51
2.5 The characteristic polynomial and eigenvalues 52
2.6 Circulant graphs 57
2.7 Eigenvalues and the combinatorial structure 60
Cospectral graphs 60
Eigenvalues, diameter and regularity 61
Automorphisms and eigenvalues 62
2.8 Comments 63
3 Categories and functors 65
3.1 Categories 65
Categories with sets and mappings, I 66
Constructs, and small and large categories 66
Special objects and morphisms 67
Categories with sets and mappings, II 68
Categories with graphs 68
Other categories 69
3.2 Products & Co
Coproducts 70
Products 72
Tensor products 74
Categories with sets and mappings, III 75
3.3 Functors 75
Covariant and contravariant functors 76
Composition of functors 76
Special functors – examples 77
Mor functors 77
Properties of functors 78
3.4 Comments 80
4 Binary graph operations 81
4.1 Unions 81
The union 81
The join 83
The edge sum 84
4.2 Products 87
The cross product 88
The coamalgamated product 89
The disjunction of graphs 92
4.3 Tensor products and the product in EGra 92
The box product 93
The boxcross product 96
The complete product 96
Synopsis of the results 97
Product constructions as functors in one variable 97
4.4 Lexicographic products and the corona 98
Lexicographic products 98
The corona 99
4.5 Algebraic properties 100
4.6 Mor constructions 102
Diamond products 102
Left inverses for tensor functors 104
Power products 105
Left inverses to product functors 106
4.7 Comments 107
5 Line graph and other unary graph operations 108
5.1 Complements, opposite graphs and geometric duals 108
5.2 The line graph 109
Determinability of G by LG 112
5.3 Spectra of line graphs 114
Which graphs are line graphs? 116
5.4 The total graph 118
5.5 The tree graph 119
5.6 Comments 120
6 Graphs and vector spaces 121
6.1 Vertex space and edge space 121
The boundary & Co
Matrix representation 123
6.2 Cycle spaces, bases & Co
The cycle space 124
The cocycle space 126
Orthogonality 128
The boundary operator & Co
6.3 Application: MacLane’s planarity criterion 130
6.4 Homology of graphs 133
Exact sequences of vector spaces 133
Chain complexes and homology groups of graphs 134
6.5 Application: number of spanning trees 136
6.6 Application: electrical networks 140
6.7 Application: squared rectangles 145
6.8 Application: shortest (longest) paths 149
6.9 Comments 152
7 Graphs, groups and monoids 153
7.1 Groups of a graph 153
Edge group 154
7.2 Asymmetric graphs and rigid graphs 155
7.3 Cayley graphs 161
7.4 Frucht-type results 163
Frucht’s theorem and its generalization for monoids 164
7.5 Graph-theoretic requirements 165
Smallest graphs for given groups 166
Additional properties of group-realizing graphs 167
7.6 Transformation monoids and permutation groups 171
7.7 Actions on graphs 173
Fixed-point-free actions on graphs 173
Transitive actions on graphs 174
Regular actions 175
7.8 Comments 177
8 The characteristic polynomial of graphs 178
8.1 Eigenvectors of symmetric matrices 178
Eigenvalues and connectedness 179
Regular graphs and eigenvalues 180
8.2 Interpretation of the coefficients of chapo(G) 181
Interpretation of the coefficients for undirected graphs 183
8.3 Spectra of trees 185
Recursion formula for trees 185
8.4 The spectral radius of undirected graphs 186
Subgraphs 186
Upper bounds 187
Lower bounds 188
8.5 Spectral determinability 189
Spectral uniqueness of Kn and Kp q
8.6 Eigenvalues and group actions 191
Groups, orbits and eigenvalues 191
8.7 Transitive graphs and eigenvalues 193
Derogatory graphs 194
Graphs with Abelian groups 195
8.8 Comments 197
9 Graphs and monoids 198
9.1 Semigroups 198
9.2 End-regular bipartite graphs 202
Regular endomorphisms and retracts 202
End-regular and End-orthodox connected bipartite graphs 203
9.3 Locally strong endomorphisms of paths 205
Undirected paths 205
Directed paths 208
Algebraic properties of LEnd 211
9.4 Wreath product of monoids over an act 214
9.5 Structure of the strong monoid 217
The canonical strong decomposition of G 218
Decomposition of SEnd 219
A generalized wreath product with a small category 221
Cardinality of SEnd(G) 221
9.6 Some algebraic properties of SEnd 222
Regularity and more for TA 222
Regularity and more for SEnd(G) 223
9.7 Comments 224
10 Compositions, unretractivities and monoids 225
10.1 Lexicographic products 225
10.2 Unretractivities and lexicographic products 227
10.3 Monoids and lexicographic products 231
10.4 The union and the join 234
The sum of monoids 234
The sum of endomorphism monoids 235
Unretractivities 236
10.5 The box product and the cross product 238
Unretractivities 239
The product of endomorphism monoids 240
10.6 Comments 241
11 Cayley graphs of semigroups 242
11.1 The Cay functor 242
Reflection and preservation of morphisms 244
Does Cay produce strong homomorphisms? 245
11.2 Products and equalizers 246
Categorical products 246
Equalizers 248
Other product constructions 249
11.3 Cayley graphs of right and left groups 251
11.4 Cayley graphs of strong semilattices of semigroups 254
11.5 Application: strong semilattices of (right or left) groups 257
11.6 Comments 261
12 Vertex transitive Cayley graphs 262
12.1 Aut-vertex transitivity 262
12.2 Application to strong semilattices of right groups 264
ColAut(S,C)-vertex transitivity 266
Aut(S, C)-vertex transitivity 267
12.3 Application to strong semilattices of left groups 270
Application to strong semilattices of groups 273
12.4 End' (S, C)-vertex transitive Cayley graphs 273
12.5 Comments 277
13 Embeddings of Cayley graphs – genus of semigroups 278
13.1 The genus of a group 278
13.2 Toroidal right groups 282
13.3 The genus of (A × Rr) 287
Cayley graphs of A × R4 287
Constructions of Cayley graphs for A × R2 and A × R3 287
13.4 Non-planar Clifford semigroups 292
13.5 Planar Clifford semigroups 296
13.6 Comments 301
Bibliography 302
Index 318
Index of symbols 324