Separable graphs, minors and the reconstruction conjecture

Annweiler, Benedikt; Koster, Arie Marinus; Triesch, Eberhard

doi:38667

Separable graphs, minors and the reconstruction conjecture = Separable Graphen, Minoren und die Rekonstruktionsvermutung

Annweiler, Benedikt^RWTH*

2019

Verantwortlichkeitsangabevorgelegt von Benedikt Annweiler M.Sc.

ImpressumAachen 2019

Umfang1 Online-Ressource (iii, 100 Seiten) : Illustrationen

Dissertation, RWTH Aachen University, 2019

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Triesch, Eberhard (Thesis advisor)^RWTH* ; Koster, Arie Marinus (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2019-10-09

Online
DOI: 10.18154/RWTH-2019-10115
URL: https://publications.rwth-aachen.de/record/771369/files/771369.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Hadwiger number (frei) ; edge-reconstruction conjecture (frei) ; graph theory (frei) ; minor (frei) ; recognizable (frei) ; reconstructible (frei) ; reconstruction conjecture (frei) ; separable graph (frei) ; treewidth (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

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.

This doctoral thesis deals with the reconstruction conjecture in graph theory. This over 70 year old conjecture asks the question of how to uniquely determine a graph by its substructures. In this particular case, one has the isomorphism types of all induced subgraphs in which, with respect to the original graph, exactly one vertex and its adjacent edges are missing. The question now is about the uniqueness of the subgraphs of a graph, that is, whether there exists exactly one graph or at least two different graphs that contain the same isomorphism types as subgraphs in the given number. The conjecture itself reads as follows: “All simple, finite and undirected graphs on at least three vertices are reconstructible.” Reconstructible means that the set of the isomorphism types of the induced subgraphs belong to exactly one graph and that there exists no other, different graph which contains the same subgraphs. Due to the lack of a universal approach to the problem, we help ourselves with the following concept. We show that a class of graphs with a certain property is reconstructible, provided that the graphs of this class have this property. Over the last decades a wide range of classes of graphs have been proven to be reconstructible by using this principle. The hope is that one day we find enough reconstructible graphclasses such that the union of these classes cover the set of all graphs and therefore will prove the correctness of the reconstruction conjecture. A second approach is to prove that certain invariants are reconstructible. This means that the value of an invariant is already determined by the induced subgraphs of the graph. In this respect we try to find a complete set of reconstructible invariants that uniquely determine a graph. In this thesis, the author shows mainly two results. Regarding the first result, the author generalizes a result of Bondy about separable graphs. Bondy was able to show that separable graphs with no vertices of degree one are reconstructible. Furthermore, he was able to show that certain separable graphs with vertices of degree one, are reconstructible, too. The author extends and generalizes Bondy’s findings, adds new insights, and thus increases the subclass of separable graphs with vertices of degree one that are reconstructible. The second result aims at graph minors. The author shows that the fact whether one graph contains a certain other graph as a minor is often reconstructible. This depends on the structure of the minor and the order and size of the original graph. For that the graph and minor are distinguished by their connectivities. In addition, the author points out that many graph invariants can be defined by certain minors. As a consequence, it is shown that the Hadwiger number and the treewidth for certain graph classes are reconstructible. The thesis concludes with a generalization of the reduction of Yang as well as the reduction of Ramachandran and Monikandan. The author shows in this regard that the problem of the reconstruction of self-complementary classes of graphs can be reduced to a smaller problem, thus simplifying potential reconstruction proofs of these classes.

OpenAccess:
PDF
(additional files)