Bicycles and Left-Right Tours in Locally Finite Graphs

Abstract

In der vorliegenden Dissertation wird der sogenannte Fahrradraum eines Graphen untersucht, welcher der Schnitt des Zyklenraums und des Schnittraums des Graphen ist. Graphen, deren Fahrradraum leer ist, heißen Fußgänger. Für die Betrachtung von Fahrrädern und Fußgängern bei plättbaren Graphen werden sogenannte Links-Rechts-Touren benutzt.

Es werden vier wichtige Resultate für endliche Graphen auf unendliche, lokal endliche Graphen übertragen. Dabei handelt es sich um den Tripartitionssatz von Rosenstiehl und Read, die Sätze von Shank, dass das Residuum einer Links-Rechts-Tour ein Fahrrad ist und dass weiterhin die Residuen der Links-Rechts-Touren eines Graphen seinen Fahrradraum erzeugen, und das Plättbarkeitskriterium von Archdeacon, Bonnington und Little. Um diese Resultate zu verallgemeinern ist es notwendig, den von Diestel und Kühn eingeführten topologischen Zyklenraum zu verwenden. Des weiteren werden Links-Rechts-Touren in unendlichen Graphen definiert und Merkmale für unendliche, lokal endliche Fußgänger untersucht.

This dissertation investigates the so-called bicycle space of a graph, which is defined as the intersection of the cycle space and the cut space of the underlying graph. Graphs that contain no non-empty bicycles are called pedestrian. In order to examine bicycles and pedestrians in planar graphs we make use of so-called left-right tours.

We extend four important results for finite graphs to infinite, locally finite graphs: The tripartition theorem by Rosenstiehl and Read; Shank's theorems that the residue of a left-right tour is a bicycle and that, moreover, the residues of left-right tours of a graph generate its bicycle space; and the planarity criterion of Archdeacon, Bonnington, and Little. In order to generalize these results it is necessary to use the topological cycle space as defined by Diestel and Kühn. Furthermore we define left-right tours in infinite graphs and study properties of infinite, locally finite pedestrian graphs.