Book on graph theory

Andrzej Ehrenfeucht, Tero Harju and Grzegorz Rozenberg:

Theory of 2-Structures

A Framework for Decomposition and Transformation of Graphs
Published by World Scientific, Singapore, 1999

Preface The aim of this book is to give a self-contained treatment of the theory of 2-structures, which provides a convenient framework for decomposition and transformation of mathematical systems, where one or several different binary relationships hold between the objects of a system. The 2-structure are intimately related to edge coloured directed graphs, and, indeed, in the second half of the book, we shall study labelled 2-structures that can be identified with these directed graphs. We use the generic name '2-structure' in order to emphasize that we investigate systems of binary relations in an abstract setting. Various methods to decompose graphs and other related mathematical structures related to them have been studied in the literature. Decompositions of combinatorial and algebraic structures are special cases of the divide-and-conquer method, where a large problem is partitioned into smaller subproblems, and a method is given to link solutions of the subproblems into a solution of the original one. The clan decomposition of 2-structure, also known as the modular decomposition or the substitution decomposition, is an example of such a decomposition -- it is closely related to the decomposition by quotients in algebra. This book covers two main topics. The 'static' part of the theory of 2-structure (Chapters 3 through 10) is concerned mainly with the decomposability and indecomposability (or primitivity). In Chapters 3 through 7 we consider 'unlabelled' 2-structure that are defined by an equivalence relation on the edges. The key notion here is that of a clan of a 2-structures g, which is a subset X of nodes such that an element y not in X cannot make a distinction between the elements of X by the equivalence relation provided by g. To make the classification of the edges more specific one adds a function labelling the equivalence classes of edges, obtaining in this way a labelled 2-structure; these structures are studied in Chapters 8 through 10. The 'dynamic' part of the theory (Chapters 11 through 15) is concerned with the local transformations (or switchings) of the 2-structure. Here the set of labels of the edges is given a group structure. In this way one obtains switching classes of labelled 2-structure, where a switching class consists of 2-structure that can be transformed into each other, and one uses the group operations, applied locally in the nodes, to induce transformations of the labels of the edges. Much of the motivation for the research presented in this book comes from the area of graph grammars, where one considers the global effect of local transformations defined through grammatical productions. We believe that (especially the dynamic part of) the theory of 2-structure enriches the study of graph grammars by making available the tools from group theory and the theory of switching. At the end of each chapter we provide notes on the references with annotations that we feel are relevant for the chapter. We have also included exercises, many of which are straightforward observations that provide an opportunity for the reader to check her/his understanding of the discussed material. Some of the exercises are more demanding, especially those that give a result from a research article. The references for these exercises are also given in the notes on references. Chapter 1 introduces the basic notions such as partial orders,semigroup, monoids, and groups. Groups are essential from Chapter 11 onwards, but they are used earlier than that in the form of automorphism groups. Chapter 2 gives, in a compact way, the graph theoretical preliminaries. Chapter 3 introduces the 2-structure, their clans and factors. The closure properties of the clans are investigated. Also, prime clans are introduced and discussed -- they will be crucial in the decompositions of the 2-structure. Chapter 4 continues the discussion of the basic notions of 2-structure, but now from a more algebraic point of view. In this chapter we study the operations of quotients and homomorphisms, and their relationships to clans. Chapter 5 makes the use of the results from Chapters 3 and 4 to prove the clan decomposition theorem. We also show that each 2-structure g has a very special 'construction tree', called the shape of g. It represents the 'canonical' construction of g. Chapter 6 is devoted to primitive 2-structure - those 2-structure that do not have nontrivial clans, and thus are indecomposable. Chapter 7 considers a subclass of 2-structure, called angular 2-structure, that results by forbidding primitivity on the lowest possible level. These 2-structure are interesting on their own, and have applications in partially ordered structures. Chapter 8 starts our journey to local transformations by modifying some of the results of the previous chapters to labelled 2-structure. The clan decomposition theorem is given another proof in this chapter. Chapter 9 considers a special topic of automorphisms of labelled 2-structure. Automorphisms are important in all algebraic and combinatorial systems, since they measure the 'inner symmetry' of the system. Chapter 10 discusses primitivity from the point of view of the labelled 2-structure. Chapter 11 considers switching of (directed) graphs. At the same time it is an introduction to the theory of switching of 2-structure. This chapter, as well as the following chapters, owe much of their motivation and results to switching of (undirected) graphs -- also known as Seidel switching. Chapter 12 defines the switching classes of the labelled 2-structure that take their edge labels from a group. This chapter also gives an interpretation of the switching from the point of view of local transformations of networks. Chapter 13 provides tools to study the switching classes. Also, we count here the number of the elements in switching classes in the case where the group of labels is finite. Chapter 14 considers the quotients for switching classes. Surprisingly enough, also the shape has a counterpart for the switching classes. Chapter 15 studies the properties of labelled 2-structure that remain invariant in a switching class, that is, those properties that remain unchanged under the local transformations of the 2-structure. The authors are grateful to their friends and colleagues, who have cooperated in the development of the theory of 2-structure. Acknowledgements are due to Joost Engelfriet, Jurriaan Hage, Henrik Jan Hoogeboom, Ross McConnell, Paulien ten Pas and Andrzej Proskurowski. We thank Rudy van Vliet for his comments on the first version of the manuscript of this book. The authors are indebted to Training and Mobility of Researchers Network General Theory of Graph Transformation Systems (GETGRATS) for supporting the collaboration on this book. A.E., T.H. and G.R. December 1, 1998