Graph Theory

Wilfried Imrich

Norbert Seifter

Groups Acting on Graphs

We study automorphism groups of transitive and almost transitive graphs in connection with the end structure and growth properties of the underlying graph. At the core of many of these investigations is Gromov's charcterization of groups of polynomial growth and its generalization to groups acting transitively on graphs. Topics persued up to now and still being investigated by our group include automorphism groups of graphs with polynomial growth, groups and graphs with linear growth, s-transitivity, covering graphs, groups acting on trees and groups of products of graphs. Furthermore, many of these concepts have been successfully applied to the investigation of the subgroup structure of free and virtually free groups. Although the primary goal of these activities are infinite graphs and groups, many important applications pertain to finite structures, e.g. the construction of graphs with large girth and contractors or expanders. Of particular interest in this respect are counting methods for subgroups of given index in free groups and related groups. In addition we started to investigate transitive directed graphs, in particular highly arc-transitive digraphs. This is a quite young field of interest which has close connections to topology. Besides structural properties of those graphs we are mainly interested in their automorphism groups.

Products of Graphs

This area is best described by 'The Product Graph Website' which is currently under reconstruction.


Algorithms and the Structure of Graphs

The enormous interest in good algorithms for the solution of large systems of linear equations, both by sequential and parallel methods, has increased the importance of structural investigations of associated networks. Thus, the research interests of our group pertaining to products of graphs, isometric embeddings of graphs into Cartesian products, efficient sequential and parallel algorithms for the decomposition of graphs into Cartesian products, realizations of metrics by graphs, eigenvalue methods for the decomposition of graphs and other problems have gained new dimensions.