Generalized tournaments and efficient orientations of graphs

• Verallgemeinerte Turniere und effiziente Orientierungen von Graphen

Surmacs, Michel; Guo, Yubao (Thesis advisor); Triesch, Eberhard (Thesis advisor)

Aachen (2021)
Doktorarbeit

Dissertation, RWTH Aachen University, 2021

Kurzfassung

Diese Dissertation beschäftigt sich sowohl mit theoretischen Ergebnissen, deren Anwendungen sich erst noch werden zeigen müssen, als auch mit algorithmischen Lösungen mathematischer Modelle, die auf praktischen Problemen basieren. In Teil I werden Verallgemeinerungen von Turnieren - d.h. Orientierungen vollständiger Graphen - studiert. Wir geben zunächst einen kurzen Überblick über bereits bestehende Resultate für Turniere und semivollständige Digraphen, die wir anschließend für weitere Klassen von Digraphen verallgemeinern. Dabei interessieren wir uns insbesondere für Aussagen über bestimmte Wege und Kreise. In multipartiten Turnieren betrachten wir beispielsweise konkurrierende Konzepte der Quasi-Länge und deren Implikationen für die Panzyklizität und Hamiltonizität in diesen Digraphen. Des Weiteren führen wir die Klasse der minimal quasi-panzyklisch c-partiten Turniere - d.h. c-partite Turniere, die genau c quasi-panzyklische Ecken enthalten - ein, beweisen die langjährige Vermutung, dass diese c Ecken ein stark zusammenhängendes Teilturnier induzieren und zeigen weitere strukturelle Eigenschaften, die in einer Charakterisierung aller minimal quasi-panzyklisch 3-partiten Turniere sowie eng verwandter Klassen von Digraphen münden. Wir verlassen dann das Reich der gerichteten Graphen, um Hyperturniere zu untersuchen, einer Erweiterung des Turnierbegriffs für gerichtete Hypergraphen. Unter anderem beweisen wir, dass stark zusammenhängende Hyperturniere eckenpanzyklisch sind und eine Ecke enthalten, deren Ausbogen alle panzyklisch sind. Wir führen verschiedene Möglichkeiten ein, Regularität in Hyperturnieren zu definieren, untersuchen notwendige und hinreichende Bedingungen für die Existenz von regulären Hyperturnieren und konstruieren einige explizite Beispiele. Schließlich beweisen wir, dass reguläre Hyperturniere, im Gegensatz zu ihren allgemeinen stark zusammenhängenden Gegenstücken, bogenpanzyklisch sind. Teil II dieser Arbeit baut dann eine Brücke zwischen ungerichteten und gerichteten Graphen. Ausgehend von einem ungerichteten Graphen untersuchen wir effiziente Methoden, um eine entsprechende Orientierung zu konstruieren. Da die meisten unserer Ergebnisse einen linearen oder polynomiellen Algorithmus liefern, der die betrachteten Orientierungen erzeugt, ist Teil II im Vergleich zu Teil I anwendungsorientierter. Wir fokussieren uns auf den orientierten Durchmesser eines ungerichteten Graphen als Maßstab für Effizienz. Da bewiesen ist, dass seine exakte Bestimmung ein NP-vollständiges Problem darstellt, präsentieren wir eine Reihe neuer oberer Schranken für den orientierten Durchmesser bezüglich einer Auswahl an Parametern (z.B. dem minimalen und maximalen Eckengrad) sowie für bestimmte Klassen von Graphen (z.B. maximal außenplanare Graphen, chordale maximalplanare Graphen und vollständige Apollonische Netzwerke). Für die meisten unserer Schranken können wir zeigen, dass sie bestmöglich sind, bis auf eine potenzielle kleine additive Konstante.

Einrichtungen

• Fachgruppe Mathematik [110000]
• Lehrstuhl für Mathematik der Informationsverarbeitung [114510]