Knauer Algebraic Graph Theory

Morphisms, Monoids and Matrices
1. Auflage 2011
ISBN: 978-3-11-025509-6
Verlag: De Gruyter
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, Band 41, 324 Seiten

Reihe: De Gruyter Studies in MathematicsISSN

Graph models are extremely useful for almost all applications and applicators as they play an important role as structuring tools. They allow to model net structures – like roads, computers, telephones – instances of abstract data structures – like lists, stacks, trees – and functional or object oriented programming. In turn, graphs are models for mathematical objects, like categories and functors.

This highly self-contained book about algebraic graph theory is written with a view to keep the lively and unconventional atmosphere of a spoken text to communicate the enthusiasm the author feels about this subject. The focus is on homomorphisms and endomorphisms, matrices and eigenvalues. It ends with a challenging chapter on the topological question of embeddability of Cayley graphs on surfaces.

Zielgruppe

Graduate and Advances Undergraduate Students of Mathematics and Computer Sciences, Researchers; Academic Libraries

Autoren/Hrsg.

Knauer, Ulrich

Fachgebiete

• Mathematik | Informatik Mathematik Algebra Zahlentheorie
• Mathematik | Informatik Mathematik Operations Research Graphentheorie
• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik

Inhaltsverzeichnis

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

Über Autor(innen)

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