
Algebraic Graph Theory
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
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.
More details
Other editions
New editions

Additional editions

Person
Content
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]
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.