% IMPORTANT: The following is UTF-8 encoded. This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.
@PHDTHESIS{Annweiler:771369,
author = {Annweiler, Benedikt},
othercontributors = {Triesch, Eberhard and Koster, Arie Marinus},
title = {{S}eparable graphs, minors and the reconstruction
conjecture},
school = {RWTH Aachen University},
type = {Dissertation},
address = {Aachen},
reportid = {RWTH-2019-10115},
pages = {1 Online-Ressource (iii, 100 Seiten) : Illustrationen},
year = {2019},
note = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
University; 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.},
cin = {113210 / 110000},
ddc = {510},
cid = {$I:(DE-82)113210_20140620$ / $I:(DE-82)110000_20140620$},
typ = {PUB:(DE-HGF)11},
doi = {10.18154/RWTH-2019-10115},
url = {https://publications.rwth-aachen.de/record/771369},
}
guest ::