Ends of graphs

Abstract

Our topic is infinite graph theory, with our focus on the ends of an infinite graph (which can be informally viewed as endpoints of rays), and their role in extensions of results known for finite graphs. Often, these extensions fail, if one does not take into account the ends of the graph, but otherwise hold. In other cases, results become more interesting when ends are considered as well as vertices. An example for the latter is the Erdös-Menger conjecture for infinite graphs (recently proved by Aharoni and Berger): we shall prove a generalization which allows for ends in the considered paths and separators. This means that in an infinite graph, we allow paths to be infinite. Moreover, considering ends on a par with vertices, we will allow these paths, then called arcs, to start or end in ends, and to pass through them. Similarly, the notion of a cycle will be generalized to that of a (possibly infinite) circle, which may pass through ends. This leads to a different notion of forests (so-called topological forests) in infinite graphs. Another aspect of the ends is that since in many ways they behave like vertices, they should be attributed a degree. We introduce such a notion as well as a concept of parity for ends. For ends of finite degree the parity will coincide with the parity of the degree, while ends of infinite degree will be classified into ‘even’ and ‘odd’. Using these concepts (arcs, circles, topological forests, degrees and parities of ends) we extend several results from finite graph theory verbatim to infinite graphs.

Die vorliegende Arbeit behandelt Themen der unendlichen Graphentheorie. Im Mittelpunkt stehen dabei die Enden eines Graphen. Unter Einbeziehung der Enden lassen sich Resultate der endlichen Graphentheorie auf unendliche Graphen übertragen, die andernfalls scheitern. Auch in anderen Fällen lohnt es, die Ecken und Enden eines unendlichen Graphen als gleichberechtigt zu betrachten. Wir erlauben daher unendliche Wege und unendliche Kreise, die durch Enden ’hindurchlaufen’: genauer gesagt sind dies homöomorphe Bilder des Einheitsintervalls bzw. des Einheitskreises, unter Verwendung der natürlichen Topologie auf dem Graphen zusammen mit seinen Enden (für lokal endliche Graphen ist dies deren Freudenthal-Kompaktifizierung). Unendliche Kreise und der daraus resultierende Zyklenraum C(G) unendlicher Graphen wurden von Diestel und Kühn eingeführt. Analog zum Gradbegriff für Ecken entwickeln wir einen Gradbegriff für Enden, der globale Forderungen wie z.B. hohen Minimalgrad auch für unendliche Graphen erlaubt. Desweiteren definieren wir die Parität bei unendlichen Grad. Diese Anpassungen der Standardbegriffe ermöglichen die wortwörtliche Übertragung folgender Ergebnisse auf unendliche Graphen:

• Charakterisierung der Graphen G, bei denen E(G) Element des Zyklenraums C(G) ist, als solche, die überall geraden Grad haben, • Erzwingung hochzusammenhängender Teilgraphen durch hohen Minimalgrad (im Endlichen ein Satz von Mader), • Nash-Williams’ Arborizitätssatz (allerdings mit einer zusätzlichen Beschränkung des Endengrades), • Gallai’s Satz, • MacLane’s Plättbarkeitskriterium, • Erzeugung des Zyklenraums durch lange Kreise (Locke).

Eines der wichtigsten Resultate ist

• Die Endenversion der Erdös-Menger Vermutung.

Diese bekannte Vermutung von Erdös erweitert den Satz von Menger auf unendliche Graphen, und ist in der Eckenversion kürzlich von Aharoni und Berger bewiesen worden. In der Endenversion sind neben Ecken auch Enden in den zu verbindenden Mengen sowie dem Trenner erlaubt.