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)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2019

Abstract

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.

Institutions

• Department of Mathematics [110000]
• Chair of Mathematics II (for Engineers) [113210]