The Theory of 2-Structures: A Framework for Decomposition and Transformation of Graphs

by Ehrenfeucht, Andrzej; Harju, T.; Rozenberg, Grzegorz

• ISBN13: 9789810240424
• ISBN10: 9810240422
• Format: Hardcover
• Copyright: 1999-10-01
• Publisher: WORLD SCIENTIFIC PUB CO INC

Summary

The theory of 2-structures provides a convenient framework for decomposition and transformation of mathematical systems where one or several different binary relationships hold between the objects of the system. In particular, it forms a useful framework for decomposition and transformation of graphs.The decomposition methods presented in this book correspond closely to the top-down design methods studied in theoretical computer science. The transformation methods considered here have a natural interpretation in the dynamic evolution of certain kinds of communication networks. From the mathematical point of view, the clan decomposition method presented here, also known as modular decomposition or substitution decomposition, is closely related to the decomposition by quotients in algebra. The transformation method presented here is based on labelled 2-structures over groups, the theory of which generalizes the well-studied theory of switching classes of graphs.This book is both a text and a monograph. As a monograph, the results concerning the decomposition and transformation of 2-structures are presented in a unified way. In addition, detailed notes on references are provided at the end of each chapter. These notes allow the reader to trace the origin of many notions and results, and to browse through the literature in order to extend the material presented in the book.To facilitate its use as a textbook, there are numerous examples and exercises which provide an opportunity for the reader to check his or her understanding of the discussed material. Furthermore, the text begins with preliminaries on partial orders, semigroups, groups and graphs to the extent needed for the book.

Table of Contents

Preface	vii
Preliminaries	1	(20)
Notations	1	(7)
Sets and functions	1	(2)
Closure operators	3	(1)
Relations	4	(2)
Equivalence relations	6	(2)
Partial orders	8	(3)
Downsets	8	(1)
Order embeddings	9	(1)
Linear orders	10	(1)
Semigroups and groups	11	(10)
Notations for semigroups and monoids	11	(1)
Free monoids (with involution)	12	(2)
Preliminaries on groups	14	(2)
Group actions	16	(1)
Free groups, commutators and verbal identities	17	(4)
Graph Theoretical Preliminaries	21	(14)
Directed and Undirected Graphs	21	(6)
Basic notions	21	(3)
Connectivity of graphs	24	(1)
Some special graphs	25	(2)
Comparability graphs	27	(8)
Transitively oriented graphs	27	(2)
Permutation graphs and cographs	29	(2)
Construction trees of cographs	31	(4)
2-Structures and Their Clans	35	(22)
Introduction and representations	35	(4)
Definition of a 2-structure	35	(2)
Isomorphic 2-structures	37	(1)
Reversibility	38	(1)
Substructures and clans	39	(8)
Substructures, clans and factors	39	(2)
Refinements and similarity	41	(1)
Reversible version	42	(1)
Graphs and packed components	43	(3)
Some special 2-structures	46	(1)
Closure properties of clans	47	(5)
Basic closures	47	(2)
Sibas: set theoretic closure properties	49	(2)
Clans of factors	51	(1)
Prime clans	52	(5)
Prime members in sibas	52	(1)
Minimal overlapping clans	53	(4)
Quotients and Homomorphisms	57	(18)
Quotients	57	(6)
Factorizations and quotients	57	(2)
Homomorphisms	59	(2)
Natural epimorphisms and decompositions	61	(2)
Clans and epimorphisms	63	(7)
Homomorphism theorem	63	(3)
Prime clans in quotients	66	(2)
Primitive quotients	68	(2)
Other operations	70	(5)
Premorphisms	70	(1)
Extensions	71	(4)
Clan Decomposition	75	(16)
The clan decomposition theorem	75	(8)
Maximal prime clans	75	(2)
Special sibas and 2-structures	77	(2)
The clan decomposition theorem	79	(2)
The relationship of sibas to 2-structures	81	(2)
The shape of a 2-structure	83	(4)
The shape and its representation as a tree	83	(1)
Same shapes	84	(3)
A construction of prime clans	87	(4)
A construction of clans	87	(1)
A construction of prime clans	88	(3)
Primitive 2-Structures	91	(18)
Small primitive substructures	91	(5)
Uniformly imprimitive 2-structures	91	(2)
Primitive substructures of 3 or 4 nodes	93	(3)
Hereditary properties	96	(3)
Local and global nodes	96	(2)
Hereditary properties	98	(1)
Critically primitive 2-structures	99	(10)
The parity theorem	99	(3)
The list of critically primitive 2-structures	102	(7)
Angular 2-Structures	109	(20)
Angularity	109	(7)
All-connectivity	109	(4)
All-connected skew angular 2-structures	113	(3)
T-structures	116	(5)
T-structures and partial orders	116	(2)
T2-structures	118	(3)
Linear orders and Schroder numbers	121	(8)
Bi-orders and linear orders	121	(1)
Uniformly imprimitive linear orders	122	(2)
Parenthesis words and Schroder numbers	124	(5)
Labelled 2-Structures	129	(18)
Introduction to l2-structures	129	(6)
Definitions	129	(3)
Substructures, clans and quotients	132	(3)
Clan decomposition of l2-structures	135	(7)
Uniqueness of decompositions	135	(3)
The shape of an l2-structure	138	(1)
Extensions	139	(3)
Graphs and their representations	142	(5)
Graphs as l2-structures	142	(1)
On comparability graphs	143	(4)
Unstable Labelled 2-Structures	147	(18)
Triangle free and unstable l2-structures	147	(8)
Removable edges	147	(3)
Internal and external nodes	150	(1)
Triangle-free l2-structures	151	(4)
Heredity in unstable l2-structures	155	(4)
The partition of nodes	155	(1)
Alternating structures	156	(1)
Degrees of nodes	157	(2)
A composition of unstable l2-structures	159	(6)
A constructive reduction of primitive l2-structures	159	(2)
Pendant components	161	(4)
Automorphisms of Labelled 2-Structures	165	(16)
Label preserving automorphisms	165	(10)
The l-automorphism groups	165	(2)
Transitivity	167	(2)
Automorphic actions on factors	169	(3)
Universality of l-automorphism groups	172	(3)
Nonpreserving automorphisms	175	(6)
Connections to l-automorphisms	175	(1)
Transitivity and associated permutations	176	(2)
Representing labels by automorphisms	178	(3)
Switching of Graphs	181	(22)
Introduction to switching	181	(7)
Definitions	181	(2)
The group of graphs	183	(2)
Switching classes	185	(3)
Structural properties of switching classes	188	(5)
A local characterization	188	(2)
Automophisms	190	(3)
Special problems on undirected graphs	193	(10)
Two-graphs	193	(1)
Eulerian graphs	194	(1)
Pancyclic graphs	195	(2)
Trees	197	(6)
Labelled Structures over Groups	203	(12)
Introduction	203	(4)
Groups and involutions	203	(2)
Selectors and switching classes	205	(2)
An interpretation in networks	207	(4)
Concurrent behaviour in networks	207	(1)
Reducing the actions to groups	208	(2)
Introducing reversibility	210	(1)
Examples for some special groups	211	(4)
The cyclic groups Z3 and Z4	211	(2)
The symmetric group S3	213	(2)
Clans of Switching Classes	215	(16)
Associated groups	215	(4)
The group of selectors	215	(2)
The group of abelian switching classes	217	(2)
Clans and horizons	219	(5)
Spanning trees	219	(1)
Horizons and constant selectors	220	(2)
Clans	222	(2)
Cardinalities of switching classes	224	(7)
Some special cases	224	(1)
Centralizers	224	(4)
Some improvements	228	(3)
Quotients and Plane Trees	231	(14)
Quotients of switching classes	231	(3)
Closure properties of clans	231	(2)
Quotients	233	(1)
Planes and plane trees	234	(11)
Planes	234	(3)
Plane trees	237	(2)
Bijective correspondence of plane trees	239	(4)
Forms	243	(2)
Invariants	245	(24)
Free invariants	245	(5)
General invariants	245	(1)
Edge monoids	246	(1)
Variable functions and free invariants	247	(3)
Group properties of free invariants	250	(8)
Abelian property	250	(2)
Graphs of words	252	(3)
Verbal identities	255	(3)
Invariants on abelian groups	258	(3)
Independency of free invariants	258	(1)
Complete sets of invariants	259	(2)
Invariants on nonabelian groups	261	(8)
General observations	261	(1)
Central characters	262	(3)
A characterization theorem	265	(4)
Bibliography	269	(10)
Notations	279	(4)
Index	283