Independence and k-independence in graphs in terms of degrees

Hoschek, Michael; Triesch, Eberhard (Thesis advisor); Guo, Yubao (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2015)
Doktorarbeit

Kurzfassung

Die Unabhängigkeitszahl eines Graphen ist die Mächtigkeit einer maximalen unabhängigen Menge, d.h. eine Menge aus Knoten, die paarweise nicht miteinander verbunden sind. Für manche spezielle Graphen ist die Unabhängigkeitszahl leicht zu berechnen. Im Allgemeinen gibt es aber keinen effizienten Algorithmus, der diese Invariante in angemessener Zeit berechnet und bildet somit ein fundamentales Problem in der Graphentheorie. Die Bestimmung der Unabängigkeitszahl für allgemeine Graphen ist ein NP-schweres Problem. Neben dem mathematischen Interesse findet die Unabhängigkeitszahl auch in vielen wissenschaftlichen und wirtschaftlichen Problemen ihre Anwendung. Dabei steht die genaue Berechnung solcher Paramter nicht im Vordergrund. Meistens reicht es eine Schranke anzugeben um zu entscheiden, ob ein Prozess durchführbar ist oder nicht. Darin liegt die Motivation, weitere Approximationen für die Unabhängigkeitszahl zu finden und existierende Schranken zu verbessern. Die Approximation der Unabhängigkeitszahl hat den Vorteil, dass nicht alle Informationen eines Graphen benötigt werden. Oft leiten sich die Schranken aus verschiedenen Parametern ab, die einfacher zu handhaben sind. In der vorliegenden Arbeit richten wir den Fokus auf Schranken, die sich aus der Gradsequenz eines Graphen berechnen. Wir haben weiterführende Erkenntnisse über bekannte Schranken und Algorithmen gewonnnen. Dabei lag unser Schwerpunkt bei der Schranke von Owen Murphy aus dem Jahr 1991. Wir haben das Verfahren für spezielle Graphentypen modifiziert und verbessert. Basierend auf dem Murphy Algorithmus haben wir eine neue untere Schranke für die k-Unabhängigkeitszahl entwickelt, welche eine Verallgemeinerung der Unabhängigkeitszahl darstellt. Es gibt Graphen die zeigen, dass unsere neue Approximation in gewissen Fällen eine Verbesserung aller bekannten Schranken ist. Motiviert durch den berühmten Satz von Paul Turán haben wir ein Problem der extremalen Graphentheorie gelöst. Unsere Formel macht eine Aussage über die minimale Anzahl von Kanten, die ein Graph mit gegebener Knotenzahl und k-Unabhängigkeitszahl haben kann. Bei diesen Untersuchungen haben wir einen weiteren Ansatz gefunden, wie man den Algorithmus von Murphy auf k-unabhängige Mengen verallgemeinern kann. Dies führte zu einer zweiten neuen Schranke für bestimmte Graphenklassen, die auch hier zu einer Verbesserung aller bekannten Schranken führte. In Erweiterung unserer Ergebnisse stellt sich in diesem Zusammenhang das Problem, die neue Schranke für allgemeine Graphen zu beweisen. Weder ein Beweis noch ein Gegenbeispiel haben wir fürunsere Hypothese gefunden, so dass die vorliegende Dissertation mit einer Vermutungabschließt.

Identifikationsnummern