% 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{Hiller:854835,
author = {Hiller, Michaela Ursula},
othercontributors = {Triesch, Eberhard and Koster, Arie Marinus},
title = {{O}n independence and $k$-independence in graphs with given
degree sequence},
school = {RWTH Aachen University},
type = {Dissertation},
address = {Aachen},
publisher = {RWTH Aachen University},
reportid = {RWTH-2022-09797},
pages = {1 Online-Ressource : Illustrationen},
year = {2022},
note = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
University; Dissertation, RWTH Aachen University, 2022},
abstract = {Graphs are a useful tool when it comes to representing
structures and dependencies and are utilised as such in
numerous disciplines of science. They appear, for example,
as street networks in route planning, as representation of
incompatible appointments in timetabling, and encode
neighbouring countries in the proof of the famous Four
Colour Theorem. It states that any map can be coloured with
only four colours without two neighbouring regions sharing a
colour. In physics and chemistry, graphs represent
structures of molecules. In biology, they are used to study
the gene regulatory networks of cells, and in social
science, they model the spread of information through social
networks. Mathematics provides rich theory about graphs in
their own rights. One of the most researched concepts is
independence in graphs, the study of subsets of non-related
elements regarding a two-dimensional relation. A famous
example is the eight queens problem: Place eight queens on a
chess board such that they do not threaten each other. In
this thesis, we examine independence in graphs that are
given only by their so-called degree sequences, i.e. we have
incomplete information about their structure. The question
arises, which statements regarding independence hold true
for all graphs corresponding to a given degree sequence. A
practical example are molecular formulas in chemistry, where
only the number of each type of atom is known, but not the
molecule's explicit structure. A molecular formula can
correspond to various molecules, each of which has different
chemical properties. The independence of a molecule's graph
representation is linked to the molecule's chemical
stability or reactivity. In this respect, assertions about
molecules with the same molecular formula are of interest.
We approach independence and the generalised concept of
$k$-independence for given degree sequences from a graph
theoretical point of view. This thesis is structured as
follows. The first chapter provides a brief overview of
graph theoretical concepts used in this work, particularly
with regard to degree sequences. In the second chapter, we
introduce the independence number and discuss lower and
upper bounds on this graph parameter. Regarding lower
bounds, we focus strongly on the residue and the values it
may take in certain graph classes of degree sequences.
Furthermore, we examine the gap between the residue and the
smallest possible independence number to assess the quality
of the residue as a lower bound. Subsequently, the
domination order among different elimination sequences is
studied and a related conjecture by Barrus is proved.
Concerning upper bounds on the independence number, the
annihilation number is introduced. We disprove a theorem
characterising graphs with equal independence and
annihilation number, stated by Larson and Pepper, and give a
new proof for restricted graph classes. The third chapter
covers $k$-independence and is structured analogously to the
second chapter. First, we consider lower bounds on the
$k$-independence number, in particular the $k$-residue. Then
upper bounds are discussed, and the annihilation number is
generalised for $k$-independence. Finally, we give a summary
on the contribution of this thesis and a brief outlook on
possible future research.},
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-2022-09797},
url = {https://publications.rwth-aachen.de/record/854835},
}
guest ::