On independence and $k$-independence in graphs with given degree sequence

Hiller, Michaela Ursula; Koster, Arie Marinus; Triesch, Eberhard

doi:10.18154/RWTH-2022-09797

On independence and $k$-independence in graphs with given degree sequence

Hiller, Michaela Ursula^RWTH*

2022

Verantwortlichkeitsangabevorgelegt von Michaela Ursula Hiller, M.Sc.

ImpressumAachen : RWTH Aachen University 2022

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2022

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
2022-10-21

Online
DOI: 10.18154/RWTH-2022-09797
URL: https://publications.rwth-aachen.de/record/854835/files/854835.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
$k$-independence (frei) ; degree sequence (frei) ; graphs (frei) ; independence (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Graphen sind ein weit verbreitetes Hilfsmittel zur Darstellung von Strukturen und Abhängigkeiten, die in zahlreichen wissenschaftlichen Disziplinen Anwendung finden. Beispielsweise werden Graphen genutzt, um Straßennetze in der Routenplanung abzubilden, Terminüberschneidungen bei der Erstellung von Stundenplänen zu vermeiden oder um Nachbarländer im Kontext des Vier-Farben-Satzes darzustellen. Dieser besagt, dass jede beliebige Landkarte mit nur vier Farben gefärbt werden kann, ohne benachbarten Regionen die gleiche Farbe zuzuweisen. In der Physik und Chemie werden Molekülstrukturen als Graphen dargestellt. In der Biologie werden Graphen zur Beschreibung von Genregulation in Zellen verwendet und in Sozialwissenschaften wird die Verbreitung von Informationen über soziale Netzwerke mithilfe von Graphen modelliert. In der Mathematik beschäftigt sich das Teilgebiet der Graphentheorie auf abstrakter Ebene mit den strukturellen Eigenschaften von Graphen. Eines der meistuntersuchten Konzepte ist dabei die Unabhängigkeit in Graphen - die Untersuchung von Teilmengen nicht-zusammenhängender Elemente bezüglich einer zweidimensionalen Relation. Ein berühmtes Beispiel dazu ist das Damenproblem: Wie können acht Damen auf einem Schachbrett platziert werden, sodass sie sich gegenseitig nicht schlagen? In dieser Arbeit untersuchen wir die Unabhängigkeit in Graphen, die nur durch ihre sogenannte Gradsequenz gegeben sind, während die genaue Struktur der Graphen unbekannt ist. Dabei stellt sich die Frage nach Aussagen, die für alle Graphen derselben Gradsequenz gültig sind. Diese Situation tritt beispielsweise in der Chemie auf, wenn lediglich die Summenformel eines Moleküls gegeben ist. Bekannt ist in diesem Fall nur die Anzahl der gleichartigen Atome, nicht aber die explizite Molekülstruktur. Zu einer Summenformel können verschiedene Moleküle mit unterschiedlichen Eigenschaften existieren, wobei die Unabhängigkeit in der Graphendarstellung mit der chemischen Stabilität oder Reaktionsfreudigkeit des Moleküls zusammenhängt. Aussagen über alle Moleküle mit derselben Summenformel sind daher von Interesse. Wir befassen uns im Folgenden mit der Unabhängigkeit und dem verallgemeinerten Konzept der $k$-Unabhängigkeit für gegebene Gradsequenzen aus graphentheoretischer Sicht. Diese Arbeit ist wie folgt aufgebaut: Das erste Kapitel gibt einen kurzen Überblick über die verwendeten graphentheoretischen Konzepte, insbesondere im Bereich der Gradsequenzen. Im zweiten Kapitel führen wir die Unabhängigkeitszahl ein und untersuchen untere sowieso obere Schranken für diesen Graphparameter. Im Abschnitt zu unteren Schranken liegt ein besonderer Schwerpunkt auf dem Residuum: Wir analysieren Eigenschaften dieser Schranke und ermitteln, welchen Wert das Residuum für bestimmte Klassen von Gradsequenzen annimmt. Außerdem wird die Differenz zwischen dem Residuum und der kleinstmöglichen Unabhängigkeitszahl untersucht, um die Güte des Residuums als untere Schranke zu beurteilen. Darüber hinaus betrachten wir die Dominanzordung zwischen verschiedenen Eliminationsfolgen und beweisen eine in diesem Zusammenhang offene Vermutung von Barrus. Im Abschnitt zu oberen Schranken für die Unabhängigkeitszahlbefassen wir uns vornehmlich mit der Annihilationszahl. Wir widerlegen eine von Larson und Pepper aufgestellte Charakterisierung von Graphen mit gleicher Unabhängigkeits- und Annihilationszahl und stellen einen neuen Beweis für eingeschränkte Graphenklassen vor. Das dritte Kapitel behandelt das Konzept der $k$-Unabhängigkeit und ist parallel zum zweiten Kapitel aufgebaut. Zunächst betrachten wir untere Schranken für die $k$-Unabhängigkeitszahl - der Fokus liegt hierbei auf dem $k$-Residuum. Anschließend befassen wir uns mit oberen Schranken für die $k$-Unabhängigkeitszahl und verallgemeinern die Annihilationszahl für die $k$-Unabhängigkeit. Abschließend ordnen wir den Beitrag dieser Arbeit in den Kontext des aktuellen Forschungsstands ein und geben einen kurzen Ausblick.

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.

OpenAccess:
PDF
(additional files)