## Graph DynamicsStudy of "graph operators" or "graph-valued functions" such as the line graph, the clique graph, the complement, and powers, raises several immediate questions: Which graphs are fixed under the operator? Which graphs appear as images of graphs? What happens if the operator is iterated? Over the last 30 years these questions have been answered and methods developed for particular operators in literally hundreds of papers on the subject. Nowhere, however, could one find a comprehensive treatment-a unification of terminology, questions, and methods. Graph Dynamics provides that comprehensive treatment. Its purpose is threefold: it serves as an introductory textbook on the topic, offers an encyclopedic survey of the literature, and reports recent research-both new tools and results on concrete operators. Part I explicitly presents graph dynamics general theory, stating general principles illustrated by application to graph operators. Part 2 addresses the operators themselves. It lists all known graph operators grouped together in families and recounts, with complete references, all that is known about the dynamical behavior of these concrete operators. Graph Dynamics is the book you need if you are looking for information on a particular operator, need a text for advanced students, or want to review collected research results presented with a common terminology. It is clearly an essential resource for anyone working in or studying algebra, combinatorics, or graph theory. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

INTRODUCTION 1 | v |

Discrete dynamical systems | 11 |

Fixed graphs | 18 |

Nonincreasing parameters and convergence | 30 |

Invariants | 36 |

Connected components | 43 |

Subgraphdefined operators | 57 |

Constructing infinite periodic graphs | 65 |

Powerlike operators | 97 |

Miscellaneous tools | 104 |

Intersection graph operators | 119 |

Other subgraphdefined operators | 132 |

Powerlike operators | 152 |

Shrinking or expanding operators | 171 |

Composed operators | 181 |

Digraph operators | 195 |

### Other editions - View all

### Common terms and phrases

1-factor behaviour biclique bipartite graph block graph cardinal number chordal graphs circuit cited in sect Clearly clique graph clique-Helly graphs comparability graph complement complete graphs composed operator convergent graphs Corollary cycle graph defined Definition diam(G diameter dicycles dipath disjoint union distinct vertices divergent dualization characterization dynasty edgeless exactly example Figure finite connected graph finite graph fixed graphs follows G as vertices Gallai graph graph G hyperedges hypergraph implies induced subgraph infinite depth integer intersection graph interval graphs inverse rays investigated isolated vertices isomorphic L-root least Lemma Let G line graph maximum degree middle graph natural number non-increasing obeys axioms out-degree path periodic graphs poset powerlike problem Proof Proposition pseudoinverse quasidigraph result retract semibasin simplex-edge cover strong component subgraph relation subgraph-defined operator subgraphs of G subset supremum Theorem transition number tree triangle vertex number vertex set vertices are adjacent W-linear whence