scientific article; zbMATH DE number 1139012

From MaRDI portal
Publication:4383848





Diese Arbeit besteht aus zwei Teilen. Im ersten Teil wird ein Endenkonzept für gerichtete Graphen eingeführt und untersucht. Sind \(\Theta\) und \(\Theta'\) zwei gerichtete Wege in einem Digraphen \(\Delta\), so bedeutet (a) \(\Theta\leq \Theta'\), daß es unendlich viele paarweise disjunkte \(\Theta\to \Theta'\)-Wege gibt und (b) \(\Theta\sim \Theta'\), daß sowohl \(\Theta\leq \Theta'\) als auch \(\Theta'\leq \Theta\) gilt. Da \(\leq\) eine Quasiordnung ist, ist \(\sim\) eine Äquivalenzrelation, und \(\leq\) induziert eine partielle Ordnung auf der Menge der \(\sim\)-Klassen, die Enden genannt werden. Es werden eine notwendige und einige hinreichende Bedingung(en) dafür vorgestellt, daß eine abstrakte Ordnung durch die Endenordnung eines Digraphen darstellbar ist. Des weiteren enthält diese Arbeit Resultate über endengleiche Ober- und Unterdigraphen, Translationen von Digraphen sowie Enden von eckentransitiven Digraphen. Die Hauptergebnisse des ersten Teils sind: (1) Jeder abzählbare Digraph mit einer Anfangsecke, in dem es kein Paar \(\leq\)-vergleichbarer \(\omega\)-Enden gibt, enthält eine \(\omega\)-endengleiche, aufspannende Arboreszenz. (2) Sei \(\Delta\) ein unendlicher, zusammenhängender und eckentransitiver Digraph. Wenn der \(\Delta\) zugrundeliegende ungerichtete Graph genau zwei Enden hat, dann ist \(\Delta\) ein gerichteter Strip. Jeder gerichtete Strip hat genau zwei zusammengesetzte Enden. Ist \(\Delta\) außerdem lokalfinit oder stark zusammenhängend und hat der \(\Delta\) zugrundeliegende ungerichtete Graph mindestens \(2^{\aleph_0}\) Enden, so hat \(\Delta\) wenigstens \(2^{\aleph_0}\) zusammengesetzte Enden. Der zweite Teil dieser Arbeit enthält eine vollständige Klassifizierung aller eckentransitiven planaren Strips. Jeder solche Strip hat einen Eckentypen \((3^6 )\), \((3^3.4^2)\), \((3^2.4.3.4)\), \((4^4)\), \((6^3)\), oder \((4.8^2)\). (Der Eckentyp eines ebenen Graphen beschreibt die zyklische Anordnug der Länder um eine Ecke des Graphen, wobei diese Anordnung bei allen Ecken die gleiche sein muß.) Der zweite Parameter der Klassifizierung, \(\kappa_\infty\) (die minimale Anzahl von Ecken, die man aus dem Graphen entfernen muß, um wenigstens zwei unendliche Komponenten zu erhalten), durchläuft \(\mathbb{N}\). Bei einigen Eckentypen ist ein dritter Parameter nötig. Dieser Parameter nimmt für festes \(\kappa_\infty\) aber nur endlich viele Werte an.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4383848)