h1

000771369 001__ 771369
000771369 005__ 20230408050105.0
000771369 0247_ $$2HBZ$$aHT020279161
000771369 0247_ $$2Laufende Nummer$$a38667
000771369 0247_ $$2datacite_doi$$a10.18154/RWTH-2019-10115
000771369 037__ $$aRWTH-2019-10115
000771369 041__ $$aEnglish
000771369 082__ $$a510
000771369 1001_ $$0P:(DE-588)1199555657$$aAnnweiler, Benedikt$$b0$$urwth
000771369 245__ $$aSeparable graphs, minors and the reconstruction conjecture$$cvorgelegt von Benedikt Annweiler M.Sc.$$honline
000771369 246_3 $$aSeparable Graphen, Minoren und die Rekonstruktionsvermutung$$yGerman
000771369 260__ $$aAachen$$c2019
000771369 300__ $$a1 Online-Ressource (iii, 100 Seiten) : Illustrationen
000771369 3367_ $$02$$2EndNote$$aThesis
000771369 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
000771369 3367_ $$2BibTeX$$aPHDTHESIS
000771369 3367_ $$2DRIVER$$adoctoralThesis
000771369 3367_ $$2DataCite$$aOutput Types/Dissertation
000771369 3367_ $$2ORCID$$aDISSERTATION
000771369 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University
000771369 502__ $$aDissertation, RWTH Aachen University, 2019$$bDissertation$$cRWTH Aachen University$$d2019$$gFak01$$o2019-10-09
000771369 5203_ $$aDie 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.$$lger
000771369 520__ $$aThis 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.$$leng
000771369 588__ $$aDataset connected to Lobid/HBZ
000771369 591__ $$aGermany
000771369 653_7 $$aHadwiger number
000771369 653_7 $$aedge-reconstruction conjecture
000771369 653_7 $$agraph theory
000771369 653_7 $$aminor
000771369 653_7 $$arecognizable
000771369 653_7 $$areconstructible
000771369 653_7 $$areconstruction conjecture
000771369 653_7 $$aseparable graph
000771369 653_7 $$atreewidth
000771369 7001_ $$0P:(DE-82)IDM00098$$aTriesch, Eberhard$$b1$$eThesis advisor$$urwth
000771369 7001_ $$0P:(DE-82)IDM00097$$aKoster, Arie Marinus$$b2$$eThesis advisor$$urwth
000771369 8564_ $$uhttps://publications.rwth-aachen.de/record/771369/files/771369.pdf$$yOpenAccess
000771369 8564_ $$uhttps://publications.rwth-aachen.de/record/771369/files/771369_source.zip$$yRestricted
000771369 8564_ $$uhttps://publications.rwth-aachen.de/record/771369/files/771369.gif?subformat=icon$$xicon$$yOpenAccess
000771369 8564_ $$uhttps://publications.rwth-aachen.de/record/771369/files/771369.jpg?subformat=icon-1440$$xicon-1440$$yOpenAccess
000771369 8564_ $$uhttps://publications.rwth-aachen.de/record/771369/files/771369.jpg?subformat=icon-180$$xicon-180$$yOpenAccess
000771369 8564_ $$uhttps://publications.rwth-aachen.de/record/771369/files/771369.jpg?subformat=icon-640$$xicon-640$$yOpenAccess
000771369 8564_ $$uhttps://publications.rwth-aachen.de/record/771369/files/771369.jpg?subformat=icon-700$$xicon-700$$yOpenAccess
000771369 909CO $$ooai:publications.rwth-aachen.de:771369$$popenaire$$popen_access$$pVDB$$pdriver$$pdnbdelivery
000771369 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-588)1199555657$$aRWTH Aachen$$b0$$kRWTH
000771369 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM00098$$aRWTH Aachen$$b1$$kRWTH
000771369 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM00097$$aRWTH Aachen$$b2$$kRWTH
000771369 9141_ $$y2019
000771369 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000771369 9201_ $$0I:(DE-82)113210_20140620$$k113210$$lLehrstuhl II für Mathematik (für Ingenieure)$$x0
000771369 9201_ $$0I:(DE-82)110000_20140620$$k110000$$lFachgruppe Mathematik$$x1
000771369 961__ $$c2019-11-22T08:30:46.310124$$x2019-11-04T10:56:37.267733$$z2019-11-22T08:30:46.310124
000771369 9801_ $$aFullTexts
000771369 980__ $$aI:(DE-82)110000_20140620
000771369 980__ $$aI:(DE-82)113210_20140620
000771369 980__ $$aUNRESTRICTED
000771369 980__ $$aVDB
000771369 980__ $$aphd