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

Hiller, Michaela Ursula; Triesch, Eberhard (Thesis advisor); Koster, Arie Marinus (Thesis advisor)

Aachen : RWTH Aachen University (2022)
Doktorarbeit

Dissertation, RWTH Aachen University, 2022

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.