Separable graphs, minors and the reconstruction conjecture

• Separable Graphen, Minoren und die Rekonstruktionsvermutung

Annweiler, Benedikt; Triesch, Eberhard (Thesis advisor); Koster, Arie Marinus (Thesis advisor)

Aachen (2019)
Doktorarbeit

Dissertation, RWTH Aachen University, 2019

Kurzfassung

Die Doktorarbeit bezieht sich auf die Rekonstruktionsvermutung in der Graphentheorie. Diese über 70 Jahre alte Vermutung geht der Frage nach, wie man einen Graphen eindeutig bestimmen kann. In diesem Falle besitzt man die Isomorphietypen aller induzierten Teilgraphen, in denen bezüglich des Ursprungsgraphen genau ein Knoten und seine adjazenten Kanten fehlen. Die Frage ist nun nach der Eindeutigkeit der Teil-graphen eines Graphen, das heißt, ob es genau einen Graphen oder mindestens zweiverschieden Graphen gibt, die die Isomorphietypen als Teilgraphen in vorgegebener Anzahl besaßen. Die Vermutung selbst lautet: "Alle einfachen, endlichen und ungerichteten Graphen auf mindestens drei Knoten sind rekonstruierbar." Rekonstruierbar bedeutet in diesem Sinne, dass die Menge der Teilgraphen in dieser Form nur Teilgraphen von genau einem Graphen sind und das kein weiterer Graph existiert, der die gleichen Teilgraphen enthält. Aufgrund des Fehlens eines universellen Lösungsansatzes zu der Fragestellung behilft man sich mit folgendem Konzept. Man zeigt das eine Menge oder Klasse von Graphen, die eine bestimmte Eigenschaft besitzen, unter Voraussetzung dieser Eigenschaft rekonstruierbar sind. Damit wurden über die letzten Jahrzehnte eine Menge von Klassen als rekonstruierbar bewiesen und man hofft, dass eines Tages eine ausreichende Anzahl an rekonstruierbaren Klassen gefunden wird, so dass diese die Menge aller Graphen überdeckt und damit die Rekonstruktionsvermutung beweist. Ein zweiter Ansatz ist zu beweisen, dass bestimmte Invarianten rekonstruierbar sind. Das heißt, dass der Wert einer Invariante bereits durch die Teilgraphen des Graphen festgelegt ist. Diesbezüglich versucht man eine vollständige Menge von rekonstruierbaren Invarianten zu finden, so dass diese einen Graphen eindeutig definieren. In der Arbeit zeigt der Autor hauptsächlich zwei Ergebnisse. Bezüglich dem ersten Ergebnis geht der Autor auf ein Ergebnis von Bondy über separable Graphen ein. Bondy konnte zeigen, dass separable Graphen ohne Knoten vom Grad eins rekonstruierbar sind. Des Weiteren konnte er zeigen, dass bestimmte separable Graphen, die Knoten vom Grad eins besitzen, auch rekonstruierbar sind. Der Autor erweitert und verallgemeinert die Ergebnisse von Bondy, fügt neue Erkenntnisse hinzu und vergrößert so die Teilklasse der separablen Graphen mit Grad eins, die rekonstruierbar sind. Das zweite Ergebnis bezieht sich auf Minoren in Graphen. Der Autor zeigt, dass der Fall, ob ein Graph einen speziellen Minor enthält oder nicht enthält, oft rekonstruierbar ist. Dies geschieht in Abhängigkeit von der Gestalt des Minors und in Abhängigkeit der Ordnung und Größe des ursprünglichen Graphens. Dafür wird eine Unterscheidung der Minoren und des ursprünglichen Graphens bezüglich ihres Zusammenhangs angewandt. Darüber hinaus weist der Autor darauf hin, dass viele Varianten in der Graphentheorie über bestimmte Minoren definiert werden können. Solche Invarianten können mit Hilfe von "verbotenen Minorensätzen" beschrieben werden. Die Arbeit selbst zeigt, dass als Folge aus der Minorenbetrachtung die Hadwigerzahl und die Baumweite für bestimmte Graphenklassen, abhängig von ihrer Ordnung und Größe, rekonstruierbar sind. Die Arbeit schließt mit einer Verallgemeinerung der Reduktionsbeweise von Yang beziehungsweise Ramachandran und Monikandan. Der Autor zeigt diesbezüglich auf, wie das Problem der Rekonstruierbarkeit von selbst komplementären Klassen auf ein kleineres Problem reduziert werden kann und vereinfacht damit potentielle Beweise dieser Klassen.

Einrichtungen

• Fachgruppe Mathematik [110000]
• Lehrstuhl II für Mathematik (für Ingenieure) [113210]