zbMATH — the first resource for mathematics

Graph dynamics. (English) Zbl 0848.05001
Pitman Research Notes in Mathematics Series. 338. Harlow, Essex: Longman Group. 233 p. (1995).
Graph dynamics means the study of families of graphs as discrete dynamical systems, i.e. the study of iterations of graph operators. The book consists of the introduction and two chapters, namely Chapter I, Theory for general operators, and Chapter II, Concrete operators. The first chapter begins with examples of dynamical systems other than graph systems; they are taken from number theory. Then the graph dynamical system is defined as the ordered pair \((\Gamma, \Phi)\) consisting of a set \(\Gamma\) of graphs and of a mapping \(\Phi : \Gamma \to \Gamma\). The first chapter develops the theory of this concept, mainly the iterations of \(\Phi\). We mention some concepts of this theory. A semibasin is a subset \(B \subseteq \Gamma\) such that \(\Phi (B) \subseteq B\). If both \(B\) and \(\Gamma - B\) are semibasins, then \(B\) is a basin. A graph parameter is any mapping from a semibasin \(\Psi\) of \(\Gamma\) into some set \(\Theta\). A root of a graph \(G \in \Gamma \) is a graph \(H \in \Gamma\) such that \(\Phi (H) = G\). If \(\varnothing \in \Gamma\) and \(\Phi (\varnothing) = \varnothing\), an \(n\)-mortal graph \(G\) is defined as a graph \(G \in \Gamma\) such that \(\Phi^n (G) = \varnothing\). The section titels of Chapter I read: 1. Discrete dynamical systems, 2. Fixed graphs, 3. Increasing parameters, divergence and depth, 4. Non-increasing parameters and convergence, 5. Invariants, 6. Connected components, 7. Subgraph-defined operators, 8. Constructing infinite periodic graphs, 9. Admissible graph posets, 10. Roots, 11. Decision problems, 12. Powerlike operators, 13. Miscellaneous tools.
The second chapter describes a lot of concrete graph operators. In Section 14, Intersection graph operators, an example is the clique graph \(C(G)\) whose vertex set is the set of all cliques of \(G\) and in which two vertices are adjacent if and only if they have a nonempty intersection. In Section 15, Other subgraph-defined operators, an example is the wing graph \(W(G)\) whose vertex set is the edge set of \(G\) and in which two vertices are adjacent if and only if they are nonadjacent edges of some induced path with 4 vertices in \(G\). In Section 16, Powerlike operators (the same section title as of Section 12), an example is the antipodal graph \(A(G) \) with the same vertex set as \(G\) in which two vertices are adjacent if and only if their distance in \(G\) is equal to the diameter of \(G\). In Section 17, Shrinking or expanding operators, examples are the centre of a graph \(G\), the total graph of \(G\), subdivisions of \(G\), etc. In Section 18, Composed operators, an example is the operator CL composed of the line graph and the clique graph. In Section 19, Digraph operators, an example is the line digraph. The bibliography at the end comprises 21 pages.
The book surveys a lot of graph operators and brings a new viewpoint for their study—investigating them as discrete dynamical systems with the main accent on the iteration of operators. It may be recommended to all that are seriously interested in graph theory and have a basic knowledge of it.

05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05Cxx Graph theory