Mathematikgebäude, M811

Circulant graphs form an important and very well-studied class of graph. They are Cayley graphs of cyclic groups and have been proposed for numerous applications such as local area computer networks, large area communication networks, parallel processing architectures, distributed computing, and VLSI design. Their connectivity and diameter, cycle and path structure, and further graph-theoretical properties have been studied in great detail. Polynomial time algorithms for isomorphism testing and recognition of circulant graphs have been long-standing open problems which were completely solved only recently. Our goal here is to extend some of the fundamental results concerning circulant graphs to the similarly defined yet more general class of distance graphs. We prove that the class of circulant graphs coincides with the class of regular distance graphs. We study the existence of long cycles and paths in distance graphs and analyse the computational complexity of problems related to their connectivity and diameter. (joint work with L. Draque Penso and J.L. Szwarcfiter)

Der Vortrag richtet sich auch an Studierende der Mathematik und der Wirtschaftsmathematik mit Vorkenntnissen in Optimierung und/oder Operations Research. (Kaffeetrinken: 15:45 Uhr)

Prof. Dr. Dieter Rautenbach

TU Ilmenau