### Contents

• Preface vii

1. #### Preliminaries

• 1.1 Notations 1
• 1.1.1 Sets and functions 1
• 1.1.2 Closure operators 3
• 1.1.3 Relations 4
• 1.1.4 Equivalence relations 6
• 1.2 Partial orders 8
• 1.2.1 Downsets 8
• 1.2.2 Order embeddings 9
• 1.2.3 Linear orders 10
• 1.3 Semigroups and groups 11
• 1.3.1 Notations for semigroups and monoids 11
• 1.3.2 Free monoids (with involution) 12
• 1.3.3 Preliminaries on groups 14
• 1.3.4 Group actions 16
• 1.3.5 Free groups, commutators and verbal identities 17

2. #### Graph Theoretical Preliminaries

• 2.1 Directed and Undirected Graphs 21
• 2.1.1 Basic notions 21
• 2.1.2 Connectivity of graphs 24
• 2.1.3 Some special graphs 25
• 2.2 Comparability graphs 27
• 2.2.1 Transitively oriented graphs 27
• 2.2.2 Permutation graphs and cographs 29
• 2.2.3 Construction trees of cographs 31

3. #### 2-Structures and Their Clans

• 3.1 Introduction and representations 35
• 3.1.1 Definition of a 2-structure 35
• 3.1.2 Isomorphic 2-structures 37
• 3.1.3 Reversibility 38
• 3.2 Substructures and clans 39
• 3.2.1 Substructures, clans and factors 39
• 3.2.2 Refinements and similarity 41
• 3.2.3 Reversible version 42
• 3.2.4 Graphs and packed components 43
• 3.2.5 Some special 2-structures 46
• 3.3 Closure properties of clans 47
• 3.3.1 Basic closures 47
• 3.3.2 Sibas: set theoretic closure properties 49
• 3.3.3 Clans of factors 51
• 3.4 Prime clans 52
• 3.4.1 Prime members in sibas 52
• 3.4.2 Minimal overlapping clans 53

4. #### Quotients and Homomorphisms

• 4.1 Quotients 57
• 4.1.1 Factorizations and quotients 57
• 4.1.2 Homomorphisms 59
• 4.1.3 Natural epimorphisms and decompositions 61
• 4.2 Clans and epimorphisms 63
• 4.2.1 Homomorphism theorem 63
• 4.2.2 Prime clans in quotients 66
• 4.2.3 Primitive quotients 68
• 4.3 Other operations 70
• 4.3.1 Premorphisms 70
• 4.3.2 Extensions 71

5. #### Clan Decomposition

• 5.1 The clan decomposition theorem 75
• 5.1.1 Maximal prime clans 75
• 5.1.2 Special sibas and 2-structures 77
• 5.1.3 The clan decomposition theorem 79
• 5.1.4 The relationship of sibas to 2-structures 81
• 5.2 The shape of a 2-structure 83
• 5.2.1 The shape and its representation as a tree 83
• 5.2.2 Same shapes 84
• 5.3 A construction of prime clans 87
• 5.3.1 A construction of clans 87
• 5.3.2 A construction of prime clans 88

6. #### Primitive 2-Structures

• 6.1 Small primitive substructures 91
• 6.1.1 Uniformly imprimitive 2-structures 91
• 6.1.2 Primitive substructures of 3 or 4 nodes 93
• 6.2 Hereditary properties 96
• 6.2.1 Local and global nodes 96
• 6.2.2 Hereditary properties 98
• 6.3 Critically primitive 2-structures 99
• 6.3.1 The parity theorem 99
• 6.3.2 The list of critically primitive 2-structures 102

7. #### Angular 2-Structures

• 7.1 Angularity 109
• 7.1.1 All-connectivity 109
• 7.1.2 All-connected skew angular 2-structures 113
• 7.2 T-structures 116
• 7.2.1 T-structures and partial orders 116
• 7.2.2 $T_2$-structures 118
• 7.3 Linear orders and Schr\" o der numbers 121
• 7.3.1 Bi-orders and linear orders 121
• 7.3.2 Uniformly imprimitive linear orders 122
• 7.3.3 Parenthesis words and Schr\" o der numbers 124

8. #### Labelled 2-Structures

• 8.1 Introduction to $\ell$2-structures 129
• 8.1.1 Definitions 129
• 8.1.2 Substructures, clans and quotients 132
• 8.2 Clan decomposition of $\ell$2-structures 135
• 8.2.1 Uniqueness of decompositions 135
• 8.2.2 The shape of an $\ell$2-structure 138
• 8.2.3 Extensions 139
• 8.3 Graphs and their representations 142
• 8.3.1 Graphs as $\ell$2-structures 142
• 8.3.2 On comparability graphs 143

9. #### Unstable Labelled 2-Structures

• 9.1 Triangle free and unstable $\ell$2-structures 147
• 9.1.1 Removable edges 147
• 9.1.2 Internal and external nodes 150
• 9.1.3 Triangle-free $\ell$2-structures 151
• 9.2 Heredity in unstable $\ell$2-structures 155
• 9.2.1 The partition of nodes 155
• 9.2.2 Alternating structures 156
• 9.2.3 Degrees of nodes 157
• 9.3 A composition of unstable $\ell$2-structures 159
• 9.3.1 A constructive reduction of primitive $\ell$2-structures 159
• 9.3.2 Pendant components 161

10. #### Automorphisms of Labelled 2-Structures

• 10.1 Label preserving automorphisms 165
• 10.1.1 The $\ell$-automorphism groups 165
• 10.1.2 Transitivity 167
• 10.1.3 Automorphic actions on factors 169
• 10.1.4 Universality of $\ell$-automorphism groups 172
• 10.2 Nonpreserving automorphisms 175
• 10.2.1 Connections to $\ell$-automorphisms 175
• 10.2.2 Transitivity and associated permutations 176
• 10.2.3 Representing labels by automorphisms 178

11. #### Switching of Graphs

• 11.1 Introduction to switching 181
• 11.1.1 Definitions 181
• 11.1.2 The group of graphs 183
• 11.1.3 Switching classes 185
• 11.2 Structural properties of switching classes 188
• 11.2.1 A local characterization 188
• 11.2.2 Automorphisms 190
• 11.3 Special problems on undirected graphs 193
• 11.3.1 Two-graphs 193
• 11.3.2 Eulerian graphs 194
• 11.3.3 Pancyclic graphs 195
• 11.3.4 Trees 197

12. #### Labelled Structures over Groups

• 12.1 Introduction 203
• 12.1.1 Groups and involutions 203
• 12.1.2 Selectors and switching classes 205
• 12.2 An interpretation in networks 207
• 12.2.1 Concurrent behaviour in networks 207
• 12.2.2 Reducing the actions to groups 208
• 12.2.3 Introducing reversibility 210
• 12.3 Examples for some special groups 211
• 12.3.1 The cyclic groups $\@mathbb Z_3$ and $\@mathbb Z_4$ 211
• 12.3.2 The symmetric group $S_3$ 213

13. #### Clans of Switching Classes

• 13.1 Associated groups 215
• 13.1.1 The group of selectors 215
• 13.1.2 The group of abelian switching classes 217
• 13.2 Clans and horizons 219
• 13.2.1 Spanning trees 219
• 13.2.2 Horizons and constant selectors 220
• 13.2.3 Clans 222
• 13.3 Cardinalities of switching classes 224
• 13.3.1 Some special cases 224
• 13.3.2 Centralizers 224
• 13.3.3 Some improvements 228

14. #### Quotients and Plane Trees

• 14.1 Quotients of switching classes 231
• 14.1.1 Closure properties of clans 231
• 14.1.2 Quotients 233
• 14.2 Planes and plane trees 234
• 14.2.1 Planes 234
• 14.2.2 Plane trees 237
• 14.2.3 Bijective correspondence of plane trees 239
• 14.2.4 Forms 243

15. #### Invariants

• 15.1 Free invariants 245
• 15.1.1 General invariants 245
• 15.1.2 Edge monoids 246
• 15.1.3 Variable functions and free invariants 247
• 15.2 Group properties of free invariants 250
• 15.2.1 Abelian property 250
• 15.2.2 Graphs of words 252
• 15.2.3 Verbal identities 255
• 15.3 Invariants on abelian groups 258
• 15.3.1 Independency of free invariants 258
• 15.3.2 Complete sets of invariants 259
• 15.4 Invariants on nonabelian groups 261
• 15.4.1 General observations 261
• 15.4.2 Central characters 262
• 15.4.3 A characterization theorem 265
• Bibliography 269
• Notations 279
• Index 283