Algebraic Graph Theory

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